[Programmers] 징검다리 (Level 4)

1. 문제 설명

 

프로그래머스

백준 플래티넘 찍고, 아무튼 취업 준비 해야 하니 요새 코테 트렌드에 맞는 프로그래머스 줄창 풀고 있었는데

이 문제는 너무 얼탱이 없어서 정리해둔다.

 

15분 컷내고 다른 문제 풀려고 넘어가는데 내 발목을 1시간이나 붙잡았다. ㅡㅡ

 

23년 이후로 테스트 케이스가 추가된 것 같다.

다른 사람들은 어떻게 풀었는지 궁금해서 뒤져봤는데, 지금 돌려보면 전부 틀린 풀이라고 나온다.

---

2. 아이디어

 

애초에 문제 카테고리가 이분 탐색이었으니, 사용할 알고리즘을 알면 문제 해결을 위한 구현은 쉬웠다.

left = 0, right = distance로 잡아두고 최소 거리를 찾아내면 그만인 문제니까.

그렇게 생각하고 아래처럼 구현을 했었다.

 

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

#define MAX 1000000000

using namespace std;
int sink;

int binarySearch(int l, int r, vector<int>& rocks, int target) {  
    int ret = 0;
    
    while (l <= r) {
        int m = (l + r) >> 1;
        
        int dist = 0, pre = 0, cnt = 0;
        for (int& rock : rocks) {
            dist = rock - pre;
            
            if (dist < m) { 
                ++cnt;
            } 
            else { 
                pre = rock;
            }
        }
        
        if (cnt > target) {
            r = m - 1;
        } else {
            ret = max(ret, m);
            l = m + 1;
        }
    }
    return ret;
}

int solution(int distance, vector<int> rocks, int n) {
    sink = distance;
    sort(rocks.begin(), rocks.end());
    return binarySearch(0, distance, rocks, n);
}

당연히 테스트 케이스 가뿐히 통과하고 제출했는데, 뭔 테스트 케이스가 30개가 넘어가길래 느낌이 싸했다.

 

띠옹?

아니나 다를까 초반엔 얼추 맞다가 뒤로 가면서 죄다 실패가 떴다.

대체 뭐가 잘못 됐나 싶어서 더 고민을 하다가, 그냥 <iostream> 헤더 불러와서 전부 찍어봤다.

 

그랬더니 아래와 같은 케이스가 문제가 된다.

중요한 건 밑에 2개.

 

거리 3, [1, 1, 2, 2]라는 바위가 주어지고, 3개의 바위를 깨야 한다고 가정해보자.

현재 로직으로는 심각한 오류가 발생한다.

제일 처음 l = 0, r = 3이므로 mid = (0+3)/2 = 1이 된다.

1. cur == 0, stone == 1 → dist가 1이므로 패스
2. cur == 1, stone == 1 → ?? 뭐야 이게
3. cur == 1, stone == 2 → dist가 1이므로 패스
4. cur == 2, stone == 2 → 또 이상한 케이스 발생

그 와중에 마지막 바위인 2와 end point인 3까지의 거리는 검사도 안 하고 있다.

이러면 깨트린 바위 수가 0이 되므로, "최소 거리를 1로 잡았더니 여유가 있네? 좀 더 늘려볼까?"라고 판단하게 되므로

l = mid + 1이 되어 다시 한 번 반복 한다.

 

l = 2, r = 3 → mid = (2+3)/2 = 2

1. cur == 0, stone == 1 → cnt = 1
2. cur == 1, stone == 1 → cnt = 2 (1이 두개라서 한 개 깼는데, 또 1이 나오는 미친 케이스 발생)
3. cur == 1, stone == 2 → cnt = 3
4. cur == 2, stone == 2 → cnt = 4 (띠옹? 넌 또 뭐야)

어찌저찌 해당 테스트는 통과할 것이다. 운이 좋았기 때문.

만약 distance = 3, [2, 2, 2, 2], n=2 라면 실패할 것이다.

 

하지만 한 가지 문제가 더 있는데, 아까부터 이상한 케이스가 나오는 문제 때문이다.

4번째 케이스를 살펴보자.

 

distance = 4, [1, 2, 2, 2, 3], n=2인 경우, {1, 3}을 개면 최소 거리 2를 얻을 수 있어야 한다.

하지만 2가 겹치는 경우 dist == 0이 되므로, 깨지 않아도 될 바위를 계속 깨느라 cnt가 n을 계속해서 넘어선다.

 

즉, 내가 놓친 것은 2가지 경우에 해당한다.

1. 같은 위치에 바위가 여러 개라면 rollback
2. distance와 비교하여 마지막에 유효하지 않으면서 깨지지 않은 바위가 있다면 모두 깨서 cnt를 갱신해야 한다.

 

1번의 경우엔 다음 위치의 rock을 확인했을 때, dist = (rock - 이전 위치) == 0일 때 다시 이전 위치로 돌려주면 된다.

        int dist = 0, pre = 0, rollback = 0, cnt = 0, rollbackCnt = 1;
        for (int& rock : rocks) {
            dist = rock - pre;
            
            if (dist == 0) {
                pre = rollback;
                dist = rock - pre;
                ++rollbackCnt;
            }
            
            if (dist < m) { 
                ++cnt;
                rollbackCnt = 1;
            } 
            else { 
                rollback = pre;
                pre = rock; 
            }
        }

여기서 중요한 건 rollback 횟수를 세주는 건데, 일반적인 플로우에서는 딱히 의미없는 숫자다.

어차피 rollback 하면서 같은 위치의 바위 계속 알아서 깨줄 테니까.

 

하지만 2의 위치에 바위가 100개가 있으면, distance에 해당하는 3과 비교해서 최솟값에 만족하지 않을 시 100개의 바위를 모두 깨주어야 한다.

즉, rollback 횟수를 모두 체크하고 마지막에 한 번에 깨주자.

 

        // 뒤에 깨지 못 한 돌 전부 카운트해야 함.
        if (sink - pre < m) {
            cnt += rollbackCnt;
        }

 

 

반례 찾느라 죽는 줄 알았네..^^

 

---

3. 코드

 

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

#define MAX 1000000000

using namespace std;
int sink;

int binarySearch(int l, int r, vector<int>& rocks, int target) {  
    int ret = 0;
    
    while (l <= r) {
        int m = (l + r) >> 1;
        
        int dist = 0, pre = 0, rollback = 0, cnt = 0, rollbackCnt = 1;
        for (int& rock : rocks) {
            dist = rock - pre;
            
            if (dist == 0) {
                pre = rollback;
                dist = rock - pre;
                ++rollbackCnt;
            }
            
            if (dist < m) { 
                ++cnt;
                rollbackCnt = 1;
            } 
            else { 
                rollback = pre;
                pre = rock; 
            }
        }
        
        // 뒤에 깨지 못 한 돌 전부 카운트해야 함.
        if (sink - pre < m) {
            cnt += rollbackCnt;
        }
        
        if (cnt > target) {
            r = m - 1;
        } else {
            ret = max(ret, m);
            l = m + 1;
        }
    }
    return ret;
}

int solution(int distance, vector<int> rocks, int n) {
    sink = distance;
    sort(rocks.begin(), rocks.end());
    return binarySearch(0, distance, rocks, n);
}