프로그래머스-징검다리

문제 링크

1. 문제 접근 과정🧐

1. 이분 탐색을 인덱스가 아닌 거리로 비교해서 탐색
2. 바위를 정렬하고 left = 0, right = distance로 시작
3. 0과 distance를 체크해야 하고 mid에 따라 제거할 바위 개수와 이전 값을 기록
4. 만약 이전과 다음 바위까지 거리가 mid보다 작으면 제거할 바위를 늘림
5. 만약 이전과 다음 바위까지 거리가 mid보다 크거나 같다면 현재 위치로 이전을 갱신
6. 제거할 바위 개수가 n보다 크면 right = mid - 1로 하여 진행
7. 제거할 바위 개수가 n보다 작거나 같으면 answer를 최대값으로 갱신하고 left = mid + 1로 하여 진행

2. 시행착오🤯

• dp를 시도하려다가 dp는 모든 경우의 수를 다 봐야한다고 판단하여 실패했다.
• 그래서 생각한 것이 이분 탐색을 거리로 하는 것(이것도 생각하는데 한참 걸렸다...)인데 다음 2가지를 놓쳤다.

1. 바위만 보고 0과 distance를 체크하지 않았음
2. 이전 값을 현재 위치로 갱신하는 로직이 없었음
   

• 오답 코드

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    vector<int> dis_min;
    sort(rocks.begin(), rocks.end());
    int l = 1 , r = distance;
    while(l <= r){
        int m = (l + r) / 2;
        int del = 0;
        for(int i = 1; i < rocks.size(); i++){
            if(rocks[i] - rocks[i -1] < m)
                del++;
        }
        if(del > n) r = m - 1;
        else{
            dis_min.push_back(m);
            l = m + 1;
        }
    }
    answer = *max_element(dis_min.begin(), dis_min.end());
    return answer;
}

3. 개선한 코드😄

• 0과 distance까지 체크하고 이전 값을 갱신하는 로직을 추가하여 해결
• 개선사항을 어차피 answer은 최솟값을 최대값이기에 벡터에 넣어 찾는 것이 아니라 max()함수로 갱신
  
• 정답 코드

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(), rocks.end());
    int l = 1 , r = distance;
    while(l <= r){
        int m = (l + r) / 2;
        int prev = 0, del = 0;
        for(int i = 0; i < rocks.size(); i++){
            if (rocks[i] - prev < m){
                del++;
            }
            else{
                prev = rocks[i];
            }
        }
        if (distance - prev < m) del++;
        if(del > n) r = m - 1;
        else{
            answer = max(answer, m);
            l = m + 1;
        }
    }
    
    return answer;
}

4. 회고💭

• 인덱스가 아닌 거리 기준 이분 탐색을 생각하는데 한참 걸렸다. 너무 생각이 틀에만 박혀있던 거 같다. 조금 더 숲을 볼 줄 알아야 한다..!!!
• 또한 구현에서 문제가 있었으며 이건 약간 고질적인 문제인 거 같은데 기초 문제를 풀면서 문법에 익숙해지고 구현이 자연스럽게 되도록 노력하자