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

문제 링크: programmers.co.kr/learn/courses/30/lessons/43236

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

1. 주의할 점

- 브루트포스로 접근하지 않는다

- 구하려는 수의 범위가 크다 + O(N^2)의 경우로는 TLE가 발생할 것 같다 → 최소 O(NlgN)의 방법으로 접근한다

 

2. 구현

- 구하려는 답의 크기가 1~10억 사이의 수 → 이분탐색으로 접근

- 파라미터로 전달받은 Rocks의 수가 정렬되어 있지 않다 -> 이분탐색을 위해 정렬

- V 벡터에는 시작점과 도착지점(Distance) 그리고 Rocks의 각 수 들의 간격을 담는다

- 바위를 N개 제거 → V의 이웃한 원소 2개를 합한다

- 바위 N개를 제거하여 바위 사이의 간격의 최소값 중에서 최대값을 도출 → V의 원소 N개를 합했을 때, 나오는 최소값중에서 최대값은? 로 바꿔서 해석할 수 있다. 총 경우의 수는 V의 크기가 M이라고 할 때, m-1Cn이다

- 위의 말을 다시 바꿔보면 다음과 같이 해석 할 수 있다. Mid보다 작은 V의 원소들을 N번 합쳐서 V의 모든 값들이 모두 Mid이상의 수를 가질 수 있는가?

- 이분탐색으로 접근을 시도하며, 합치려는 원소가 V[idx]인 경우 합치는 수를 줄이기 위해 최대한 오른쪽과 합치도록 한다(이해가 안된 경우, 아래 TC를 통해 이해를 시도)

TC #1
V원소: 5 3 2
Mid: 4

왼쪽으로 합치기: 2
오른쪽으로 합치기: 1

 

- Idx가 현재 번호, Cnt가 현재까지 합친 수를 의미하며, While문을 통해 몇 번 합쳐야하는지 계산한다

- Cnt<=N인 경우, 합칠 횟수가 여유롭거나 딱 맞으므로 Mid를 높여서 최대의 Answer를 구한다

- 이외의 경우, 합쳐야하는 횟수가 모자르므로 Mid를 낮춘다

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    vector<int> v;
    sort(rocks.begin(),rocks.end());
    int cur=0;
    for(int i=0;i<rocks.size();i++){
        int loc = rocks[i];
        v.push_back(loc-cur);
        cur = loc;
    }
    v.push_back(distance-cur);
    int len = v.size();
    int l=0,r=1000000000,mid;
    while(l<=r){
        mid = l + (r-l)/2;
        int idx=0,cnt=0;
        while(idx<len){
            int val = v[idx];
            if(val<mid){        //합쳐야 하는 경우
                while(1){
                    if(cnt==n){     //더 이상 합치지 못하는 경우
                        cnt++;
                        break;
                    }
                    if(idx!=len-1){     //뒤로 합칠 수 있는 경우
                        int next = v[++idx];
                        val+=next;
                        cnt++;
                        if(val>=mid)    break;                        
                        else{       //뒤로 더 합쳐야 하는 경우
                            //계속 진행
                        }
                    }
                    else{       //앞으로 합쳐야 하는 경우(앞은 이미 기준 넘어섬)
                        cnt++;
                        break;
                    }
                }
            }
            else{       //기준 충족하는 경우
                
            }
            idx++;
        }
        if(cnt<=n){     
            l = mid+1;
            answer = mid;
        }
        else{       //합칠 갯수가 부족한 경우
            r = mid-1;
        }

    }
    return answer;
}