Programmers_Level3_징검다리 건너기

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

프로그래머스

 

---

징검다리를 건널 수 있는 최대 인원을 구하는 문제인데 

한번에 건널 수 있는 k의 크기를 알려줘서 뭔가 보자마자 Sliding Window가 생각이 났다. 

 

가장 멀리 뒬 수 있는 거리 == k == 창문의 크기로 정하고 

그 중에 제일 큰 수들 중에 제일 작은 수를 하면 될거 같았다

 

창문안에서 제일 큰 수 == 현재 징검다리 최대로 건걸 수 있는 인원의 수

제일 큰 수들 중에서 제일 작은 수 == 전체 징검다리에서 건널 수 있는 최대 인원의 수

 

deque을 사용해서 deque.front()보다 큰 숫자를 만난다면 deque을 비우고 

deque.front()보다 작은 숫자는 넣어둔다. 

창문의 크기만큼 idx가 이동했다면 해당 창문에서 제일 큰 숫자와 정답을 비교하여 작은 숫자를 업데이트 한다. 

그리고 그 제일 큰 숫자가 창문의 범위를 넘어가면 deque에서 뺀다. 

int solution(vector<int> stones, int k) {
    int answer = INT_MAX;
    deque<int> dq; 
    
    for(int idx = 0; idx < stones.size(); ++idx)
    {
        if(!dq.empty() && dq.front() <= idx - k) 
        {
            dq.pop_front();
        }
        
        while(!dq.empty() && stones[dq.back()] <= stones[idx])
        {
            dq.pop_back();
        }
        
        dq.push_back(idx);
        
        if(idx >= k -1)
        {
            answer = answer < stones[dq.front()] ? answer : stones[dq.front()];
        }
    }
    
    return answer;
}

 

 

같이 스터디하는 알고리즘 천재가 이분탐색으로 풀어서 알려주었다. 

처음엔 이해가 잘 안되었는데 찬찬히 코드를 보니 이해가 되었다. 

 

Left = 1, Right = 징검다리의 제일 큰 값, Mid = Left와 Right의 중간값으로 한다. 

이는 최대로 건널 수 있는 인원을 이분탐색해 가는 것이다. 

 

징검다리를 건너며 징검다리의 값이 Mid보다 작다면 count를 올리고 크다면 count = 0으로 하여

Count값이 k값과 같거나 크다면 정답은 Mid의 왼쪽에 있는 것이고

Count값이 k값보다 작다면 정답이 Mid의 오른쪽에 있는 것이다. 

 

Mid 보다 징검다리의 값이 작다 => Count 올림 == 연속해서 건널 수 있음

Mid 보다 징검다리의 값이 크다 => Count 0 == Mid보다 더 많은 인원이 건널 수 있음

 

요래조래해서 Left의 값이 정답이 된다. 

 

마치 롤토체스에서 승리의 조합을 몇가지를 외우고 상황에 맞춰쓰듯이

알고리즘도 여러가지 방법을 기억하고 문제에 따라 적용할 수 있는거 같다. 

알고리즘 범부라도 다양한 문제를 풀면서 내 알고리즘 해법영역을 늘려가야겠다