프로그래머스 - 2019 카카오 개발자 겨울 인턴십 징검다리 건너기

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

 

 

 

모든 나니즈들은 강을 건널 때 모든 돌다리를 다 밟아야 한다. 즉, 한 명이 건널 때마다 모든 돌다리의 밟을 수 있는 횟수는 전부 1씩 감소하게 된다.

 

한 번에 나니즈들이 이동할 수 있는 간격은 K이다. 그러므로 나니즈가 몇 명 건넜을 때 돌다리 중에 K + 1 이상이 되는지 파악하면 된다.

 

하지만, 위의 내용대로 매번 배열의 값을 -1씩 갱신하는 코드를 작성하면 대략 200,000,000 * 200,000번의 연산이 발생하므로 시간 효율성을 통과할 수가 없을 것이다.

 

그래서 전체 배열을 순회하는 횟수를 최소화하면서, 돌다리의 간격이 K + 1 이상이 생기는 나니즈 명 수를 예측해야 한다. 전체 배열 최소 순회를 위해서 시간 복잡도 O(N)이 발생하는 슬라이딩 윈도우(투 포인터)로 탐색을 한다. 슬라이딩 윈도우의 간격을 K로 정하고 K안의 값들 전부가 언제 0이 되는지 예측하면 된다.

 

각 구간이 전부 0이 되는 값은 각 구간에서 해당 구간에서 최댓값에 해당한다. 최댓값이 0이 되는 순간 나니즈는 K + 1의 간격을 뛰어야 하기 때문이다.

위의 사진에서 5가 값이 0이 되는 순간 나니즈는 돌다리를 건널 수 없게 된다.

그러므로 우리는 k간격의 윈도우를 처음부터 배열 끝까지 순회하면서 해당 경우의 수 별로 간격에서 최댓값이 얼마인지 알아내기만 하면 된다.

 

그런데 K간격 안에서 최댓값을 귀하기 위해서 2중 for문을 돌게 되면 O(N^2)의 시간 복잡도를 갖게 되고 시간 효율성에서 분명 틀리게 될 것이다.

그래서 우리는 좀 더 효율적으로 구간 내의 최댓값을 구하는 방법이 필요하다. 이럴 때 필요한 게 Heap을 이용한 최댓값 탐색이다. (Heap 구조는 시간 복잡도 O(lgN)으로 최댓값이나 최솟값을 뽑아낼 수 있다. 탐색 자체가 내부적으로 이분 탐색과 완전히 동일하다.)

해당 이미지는 https://blockdmask.tistory.com/88에서 퍼왔습니다. map과 multimap 궁금하면 링크로

 

하지만 단순히 Heap 구조를 사용하면 슬라이딩 윈도우가 오른쪽으로 이동하면서 Heap 내부에서 어떤 값을 빼야 할지 알 수가 없다. 따라서 내부적으로 Heap 구조를 가지고 있고, Key와 value 값의 구조를 갖는 Map을 사용할 것이다.

 

우리는 각 돌다리의 건널 수 있는 횟수를 가지고 Heap을 정렬해야 하므로 Map의 Key값을 돌다리 횟수로 Value값을 인덱스 값으로 하겠다. 그리고 Key값(돌다리 횟수)이 같을 수 있으므로 Multimap구조를 사용하다.

 

(추가적인 디데일)

그리고 값을 제거할 때는 index값을 가지고 Value를 구하고 해당 Value값의 pair쌍을 제거할 것이다. 이때, Key(돌다리 횟수) 값이 같을 수 있기 때문에 Key값이 같다면 인덱스가 작은 값이 먼저 나오도록 Value(인덱스) 값을 음수로 저장한다.

 

 

이렇게 모든 K간격을 순회하면서 가장 K+1 간격이 빨리 발생하는 지점의 값을 구하면 된다.

 

 

추가적으로 map에서 최댓값은 m.end() - 1로 접근할 수 있다.

 

 

#include <string>
#include <vector>
#include <map>
#define INF 987654321

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    
    // 디딤돌의 밟을 수 있는 횟수로 값을 정렬하고 싶으므로 key를 밟을 수 있는 횟수로, 
    // index값으로 key를 찾아야 할 경우가 있으므로 value로 index를 넣어준다.
    // (밟을 수 있는 횟수, index)
    multimap<int, int> m;
    multimap<int, int>::iterator iter;
    
    
    // k간격만큼 stones[i]를 포함시켜 k길이의 간격들을 만들어둔다.
    // value값으로 자동 정렬될 때, value가 같은 값을 가질 수 있다.
    // 이 경우 index가 작은 값을 먼저 탐색하기 위해서 index에 음수를 취해준다.
    for(int i = 0; i < k; i++) {
        m.insert({stones[i], -i});
    }
    
    // 맨처음 시작에서도 min값이 나올 수 있다.
    int min = INF;
    iter = m.end();
    int max = (*--iter).first;    
    if(min > max) min = max;
    
    // k간견을 갖는 multimap에 원소 하나를 추가하고, 가장 마지막 원소 하나를 빼준다.
    // multimap 안에서 가장 최대값이 min보다 작으면 min을 그 최대값으로 덮어써준다.
    for(int i = k; i < stones.size(); i++) {
        iter = m.find(stones[i - k]);
        m.erase(iter);
        m.insert({stones[i], -i});
        
        iter = m.end();
        int max = (*--iter).first;
       
        if(min > max) min = max;
    }
    
    answer = min;
    
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~