[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기

https://programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

단순히 반복문 돌려가면서 징검다리 숫자를 1씩 빼 주는 방식으로 푸는 문제가 아니라는 것은 너무나도 당연해 보인다.

 

징검다리의 처음 상태

3번째 친구가 징검다리를 건넌 후. k=3이므로 4번째 친구는 건너지 못한다.

 

이 문제는 결국 각 징검다리 숫자에서 n씩 뺐을 때, 0보다 작거나 같은 돌이 최소 연속 k개 있게끔 만드는 n의 최솟값을 구하는 문제이다.

=> 이걸 더 단순화 시키면, 징검다리의 연속된 돌을 k개 묶어서 돌에 적힌 숫자의 max를 구한 뒤, max 중 가장 작은 값을 구하는 문제와 같다.

 

예시의 경우

2 4 5 3 2 1 4 2 5 1

max 값이 가장 작아지는 경우는 3,2,1을 묶었을 때이고 이때의 max값이 3이므로 정답은 3이 된다.

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> stones, int k) {
	int answer = 0;

	int max = -1;
	int min_max = 200000001;

	// max값과 비교하면서 for문
	for (int i = k - 1; i < stones.size(); i++) {
		// 새로 max값 계산하는 경우
		if (max <= i - k) {
			int temp_max = i - k + 1;    // 새로 계산하는 범위의 첫 원소

			// 두번째 원소부터 for문 돌려가며 temp_max 계산
			for (int j = i - k + 2; j <= i; j++) {
				if (stones[temp_max] < stones[j]) {
					temp_max = j;
				}
			}

			max = temp_max;
			if (stones[temp_max] < min_max) min_max = stones[temp_max];
		}
		// 이전 max와 비교하는 경우
		else {
			if (stones[max] < stones[i]) {
				max = i;
				if (stones[max] < min_max) min_max = stones[max];
			}
		}
	}

	answer = min_max;

	return answer;
}

 

 

처음에 짠 코드.

이것도 나름 효율적으로 짜보고자 노력했으나 징검다리의 돌들이 모두 내림차순으로 정렬되어 있는 경우 아무런 효과가 없었다.ㅋㅋㅋ

결국 효율성 테스트케이스 하나를 통과하지 못함ㅠ

 

#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int min_max;

    multiset<int> s;

    for (int i = 0; i < k; i++) {
        s.insert(stones[i]);
    }

    min_max = *(--s.end());

    for (int i = k; i < stones.size(); i++) {
        int erase_num = stones[i - k];
        s.erase(s.find(erase_num));
        s.insert(stones[i]);

        min_max = min(min_max, *(--s.end()));
    }

    answer = min_max;

    return answer;
}

 

다른 분들의 코드를 보고 다시 작성한 코드.

k개 돌의 정보를 set에다가 넣어놓으면 시간복잡도를 줄일 수 있다.