[프로그래머스] 징검다리 C++

programmers.co.kr/learn/courses/30/lessons/43236#

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

 돌 사이 거리를 새로운 벡터로 만들어 문제를 풀려고 했는데 이분탐색을 적용할 방법이 떠오르지 않았다.

 

 

1. 풀이.

 문제의 실마리는 돌 간 거리의 최소값을 이분탐색으로 찾아가는 것이다. 이 때 이분탐색의 기준은 돌 간 거리가 아니라 제거된 돌 개수이다. 

 찾는 값과 기준이 되는 값이 다르기 때문에 문제 해결이 더 어렵고, 다른 사람의 해답을 처음 봤을 때 뭔지 이해가 안됬다.

 그러니까 돌 간 거리의 최소값이 정답과 가까워지게 이분탐색을 실행할 것이고, 그 기준을  제거된 돌 개수로 하겠다는 풀이다. 이때 제거된 돌 개수가 문제에서 제시한 제거 개수 n보다 크냐 작냐까지 비교할 수 있다면 이분탐색 코드를 완성할 수 있다.

int solution(int distance, vector<int> rocks, int n) {
    sort(rocks.begin(), rocks.end());
    int left=1;
    int right= distance;
    
    // 1. answer가 1에서 시작하는 이유는?
    int answer = 1;
    while(left<=right){
        int minDist = (left+right)/2;
        int removed=0;
        int prev = 0;
        for(int rock:rocks){
            int dist = rock-prev;
            if(dist<minDist){
                removed++;
            } else {
                prev = rock;
            }
        }
        if(distance-prev < minDist) removed++;
        
        if(removed>n){
            right = minDist-1;
        } else{
        	// 2. if(removed==n)이 필요없는 이유는?
            answer = max(answer, minDist); // 3. max를 구하는 이유는?
            left = minDist+1;
        }
    }
    return answer;
}

2. 의문 

1.  answer가 1에서 시작하는 이유는?

 같은 이분탐색 분류의 문제, '입국심사'에서 초기 answer값을 Max로 설정해야하는 이유가 있었다. 예제에 따라 while loop를 돌면서 answer가 업데이트되지 않고 종료되는 경우가 생기는데, 이때 answer값을 Max로 설정해두면 Max값 부터 탐색을 한 번 더 돌 수 있었다. 여기선 answer값이 1에서 시작한다. rocks[0]에서 시작하면 안되나? 모르겠다.

 

 이분 탐색은 어짜피 중간값을 기준으로 탐색을 진행하기 때문에, lowerBound와 upperBound가 범위보다 커도 상관없다. 어짜피 어마어마하게 큰 수를 계산하기 위하여 이분 탐색을 사용하는 거니까. 문제를 풀 때는 대충 제일 작은값과 제일 큰값을 Min과 Max로 두고 풀고, 다 풀고 난 다음에 생각하는게 빠를 것 같다.

 

 2. if(removed==n)을 사용하면 안되는 이유는?

 내 생각에 문제의 조건을 정확하게 만족할 때에만 정답을 업데이트 해야한다. 그런데 제거된 돌이 n보다 적을 때에도 minDist가 업데이트 된다. 이것 때문에 잘못된 값이 업데이트가 되면 어떻게 할까?

 

  일단 로직을 보자. answer은 초기값이 1이고 whileLoop가 진행되면서 점점 더 큰 값으로 업데이트 된다.  그리고 이분탐색에 의해 removed는 점점 더 정답 쪽으로 수렴해나간다. 이때 removed와 minDist의 관계를 이해해야 한다. removed가 정답 쪽으로 수렴해나갈 때 minDist는 어떻게 변화하는가? 

 

 minDist를 정답보다 크게 가정했다면 removed는 기준보다 커지고, minDist를 정답보다 작게 가정했다면 removed는 기준보다 작아진다. 따라서 removed가 기준보다 클 때 minDist도 정답보다 크고, removed가 기준보다 작을 때 minDist는 정답보다 작다. 

 

 removed가 정답을 향하여 수렴하기 때문에 더 늦게 updates 된 minDist 값이 더 정확한 값인 것은 분명하다. 하지만 그것은 추정이 아닌가? 정답에 가까워 지는 것이지 문제의 조건을 만족하는 정확한 값이 나온다고 보장할 수 있는가?

 

 만약 문제의 조건을 만족하는 정확한 값 바로 직전에 while loop가 끝나면 어떻게 되는가? loop가 끝나기 직전을 생각해보자. left<=right가 while Loop가 진행되는 조건이므로 마지막 loop는 left==right에서 끝나게 된다. 따라서 정해진 UpperBound와 LowerBound 사이에서 최적의 값 하나를 찾았다는 소리다.

 여기까지 생각해보니 뭔지 알겠다. 문제에서는 항상 정답이 존재하므로 UpperBound와 LowerBound 사이에 항상 답이 있다면 left==right가 되는 지점에서 답이 나올 수 밖에 없다.

 

  OK 그럼 if(rmoved==n)가 없어도 정답이 나오는 이유를 알겠다.

 그럼 if(removed==n)를 코드에 넣었을 때 실패 케이스가 나오는 이유는 무엇인가? 이 사례를 확인하려면 Edge Case를 찾아야 한다. 실패 케이스를 직접 찾아봐야 확인할 수 있을 것 같다. 

 

3. max로 구현하는 이유는? 

 answer는 최대값을 구하는 문제이다. 최솟값의 최대값을 구하라고 하였기 때문에 헷갈린다. 최솟값 조건은 minDist로 이미 구해놓았다. 따라서 이 값 중에 최대 값을 구하면 된다. 이때 removed >n 조건은 answer 값이 줄어들 것이므로 업데이트를 할 필요가 없다. removed < n 일때 removed값을 늘릴 것이고, 이 때 minDist도 함께 늘어날 것이므로 이 때의 값을 찾으면 된다. 

 위에서 이야기 한 바와 같이, left==right에서 멈출 것이기 때문에 이 값을 반환하면 된다.

 

 아직도 조금씩 가물가물 한게  if( removed==n )라는 조건이 있어야 minDist가 의미있어지는 것이 아닌가?

모르겠다.

 

아래 블로그에서 많은 도움을 받았다.

taesan94.tistory.com/154