[C++] 프로그래머스 징검다리 건너기 풀이

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

코딩테스트 연습 - 징검다리 건너기

문제의 카테고리가 이분탐색인 것을 알지 못하고 문제를 본다면 이분탐색을 이용하여 문제를 풀어야 한다는 것을 알아차리기가 쉽지 않다. 며칠 전에 이분탐색 여러 문제를 풀어보았기 때문에 문제를 읽고 이분탐색을 사용하면 잘 될 것이라고 생각하여 문제 접근 방향을 그렇게 정하였다. 코드는 굉장히 짧다. 아래와 같다.

 

소스코드

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

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int left = 0, right = *max_element(stones.begin(), stones.end()) + 1; //초기값 설정
    for(int i = 0; i < 30; i++) { //최대 200000000이므로 log2 200000000은 30보다 충분히 작으므로 가능하다.
        int mid = (left + right) / 2; //중간 값을 설정한다. mid명이 건넌다고 생각한다.
        int maxcnt = 0; //가장 많이 건너뛴 수를 저장
        int cnt = 1; //건너뛴 횟수를 그때그때 저장
        for(int i = 0; i < stones.size(); i++) { //징검다리를 하나씩 보며
            if(stones[i] < mid) cnt++; //mid번째 사람이 건널 경우 mid보다 작은 값이 있는 돌은 mid-1명만 건널 수 있으므로 건너뛰게 된다. 따라서 숫자를 센다.
            else { //만약 mid보다 크거나 같은 경우 mid번째 사람도 돌을 밟을 수 있으므로 한번에 건너뛰는 돌의 수는 1로 다시 초기화하고 현재 돌까지 한번에 건너뛴 돌의 수를 계산
                maxcnt = max(maxcnt, cnt); //한번에 건너뛴 돌의 최대값 갱신
                cnt = 1;
            }
        }
        maxcnt = max(maxcnt, cnt); //마지막 돌까지 건널때 cnt값이 갱신되지 않을 수 있으므로 한 번 더 체크
        if(maxcnt <= k) left = mid; //최대 k개 건너 뛸 수 있으므로 가장 많이 건너뛴 수가 k보다 작거나 같은 경우 더 많은 인원이 건널 수 있다고 판단
        else right = mid; //그렇지 않으면 더 적은 사람이 건너 뛸 수 있다고 판단
    }
    answer = left; //등호가 left에 있으므로 left값이 최종 결과
    return answer;
}

이분탐색을 할 때 결과값이 left냐 right냐를 아는 것은 꽤 어렵다. 이 문제는 최대값을 구해야하는 문제이므로 등호를 포함하는 값이 정답이 될 것이다. 글쓴이는 거의 left에 등호를 붙인다.

 

풀이에서 중요한 부분

 

    1. left는 초기값으로 0, right는 최대값보다 1 큰 값으로 설정하였다. 1을 더한 이유는 만약 left = 5, right = 6일 경우 mid값으로 갱신했을 경우 mid는 항상 5이므로 left는 6이 될 수 없다. 만약 정답이 6일 경우 오답이 나올 수 있다. 따라서 left는 최소값보다 작은 값, right는 최대값보다 큰 값으로 설정하는 것이 좋다.

 

    2. for문을 30번 돌았다. stone배열의 원소의 최대값은 200000000(2억)이다. 따라서 2억을 커버할 수 있는 30으로 설정하였다. log2의 200000000은 30보다 훨씬 작은 수이다. 2^30은 대락 10의 9제곱이기 때문이다. 2억을 넘을 수 있는 log값으로 더 작은 수로 설정하여도 충분히 돌아간다.

 

    3. left가 정답인 이유는 파라매트릭 문제를 여러번 풀어봐야한다. 이 문제에서는 건너뛴 바위의 수가 k보다 작거나 같은 조건에서 가장 큰 값이어야한다. 이때 for문의 가장 마지막에 if(maxcnt <= k) left = mid;라는 코드가 있다. 이 코드가 바로 이전 말과 같은 말이다. 건너뛴 바위의 수가 k보다 작거나 같을 때 left를 mid로 설정하라는 말이다. 더 큰 값이 있을 수 있기 때문이다. 만약 이 조건을 만족하지 않을 경우 right = mid 코드가 실행될 것이다. 따라서 left는 정답이 될 수 있는 조건을 만족하지 않은 상태에서 최대값으로 갱신되기 때문에 left가 최종 정답이 되는 것이다.