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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 생각 났던 풀이는 가장 짧은 거리를 찾은 다음 어떤 돌을 제거할지 선택하는 방법이다.

하지만 이 방법은 최악의 경우 시간복잡도가 O(N^2)이 되기 때문에 다른 방법을 생각했다.

 

그러다가 바위 사이의 최소 거리를 정한 다음 돌을 몇 개 제거해야 하는지 계산하면 더 빠르게 연산이 될 것이라는 생각이 들었다.

여기서 바위 사이의 최대 거리는 도착점까지의 거리이므로 min Distance = 1, max Distance = 도착점까지의 거리로 이분탐색을 하도록 코드를 구현했다.

 

예를 들어 돌 사이의 최소 거리가 4라고 하면, 돌 A와 돌 B 사이의 거리는 최소 거리인 4보다 커야한다.

만약 돌 A, B 사이의 거리가 4보다 작은 경우 돌을 제거하면 된다.

이렇게 제거한 돌의 개수가 n보다 큰지, 작거나 같은지를 비교하도록 이분탐색을 했다.

 

위 그림과 같이 시작점과 돌들이 주어졌을 때, 최소 거리가 4인 경우에 돌을 몇개 제거해야하는지 계산해 보자.

 

먼저 0과 3사이의 거리는 3이므로 3번 돌을 제거한다.

이후 0과 6사이의 거리는 6이므로 돌을 제거하지 않는다. (이 때 기준이 되는 돌이 0에서 6으로 바뀐다.)

6과 10 사이의 거리는 4이므로 돌을 제거하지 않는다.

 

위 과정을 반복해 제거 한 돌의 수를 계산하고 그 수가 n이하면, 최소거리를 4로 할 수 있으므로 거리를 더 늘릴 수 있는지 계산한다.

 

+ 이 때, 바위 사이의 거리는 정렬이 되지 않은 상태이므로 정렬을 해주어야 한다.

 

이후 돌 사이의 최소거리의 최대값을 return하면 된다.

 

​

[아이디어 정리]

1. 돌을 오름차순으로 정렬하고, 도착점을 끝에 넣는다.
2. 최소거리를 d로 했을 때 돌을 몇개 제거해야 하는지 계산한다.
3. 만약 제거해야하는 돌이 n보다 크면, 불가능 하므로 ed = mid-1로 바꿔서 다시 탐색을 한다.
4. 만약 제거해야하는 돌이 n이하라면, 가능하므로 st = mid+1로 바꿔서 다시 탐색을 한다.
5. 계산이 끝난 후 가능한 최대 거리를 return한다.

 

 

Code

 

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    // 반대로 거리를 기준으로 찾는다.
    int answer = 0;
    int st=0, ed=distance, mid=0;
    sort(rocks.begin(),rocks.end());
    rocks.push_back(distance);
    while(st<=ed)
    {
        mid =(st+ed)/2;
        int prevRock=0;
        int rockCnt=0;
        for (int i=0; i<rocks.size(); i++)
        {
            if (rocks[i]-prevRock<mid) //제거해주어야 하는 돌들
            {
                rockCnt+=1;
            }
            else
            {
                prevRock=rocks[i];
            }
        }
        if (rockCnt>n)// 제거할 돌이 많다면 거리가 멀다는 뜻
        {
            ed=mid-1;
        }
        else
        {
            answer=mid;
            st=mid+1;
        }   
    }
    return answer;
}

 

---

탐색을 해야하는 문제들을 최근에 많이 봤는데, 단순 탐색으로 시간 복잡도에서 초과가 날 것 같은 문제들은 특정한 기준을 잡아야 하는 문제들이 많은 것 같다.

비슷한 탐색 문제가 나온다면 시간 복잡도를 잘 생각해 보고 어떤 값을 기준으로 탐색을 해야할지 고민해보자

프로그래머스