[프로그래머스 Level 4] [이분탐색] 징검다리 (C++)

안녕하세요! 코딩하는 경제학도 쏘코입니다.

오늘 문제는 새로운 시야에서 문제를 바라볼 수 있게 해준 그런 문제였습니다.

이분탐색이 참 떠올리기 어려운데 떠올릴 수만 있으면 알고리즘 자체는 쉽게 반복되는 패턴이라 (start, mid, end) 구현은 크게 어렵지 않습니다.

다만 저는 이번 문제에서 아이디어를 떠올리는 데 굉장한 시간이 걸렸다는거...

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/43236

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

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가

programmers.co.kr

0. 문제 설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.

예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치	각 바위 사이의 거리	거리의 최솟값
[21, 17]	[2, 9, 3, 11]	2
[2, 21]	[11, 3, 3, 8]	3
[2, 11]	[14, 3, 4, 4]	3
[11, 21]	[2, 12, 3, 8]	2
[2, 14]	[11, 6, 4, 4]	4

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

0.0. 제한사항

도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
바위는 1개 이상 50,000개 이하가 있습니다.
n 은 1 이상 바위의 개수 이하입니다.

0.1. 입출력 예

distance	rocks	n	return
25	[2, 14, 11, 21, 17]	2	4

0.2. 입출력 예 설명

문제에 나온 예와 같습니다.

1. 풀이 과정

문제를 딱 읽고 바로 떠올리기는 쉽지 않지만, 문제를 있는 그대로가 아닌 조금 다르게 해석해보면 쉽게 접근할 수 있습니다.

바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 찾는 것이 문제이지만, 현재 각 지점 사이의 거리의 한계를 지정하고, 그것보다 작은 간격을 가진 돌을 빼서 찾을 수도 있습니다. 저는 후자의 방식을 이용해서 이분탐색을 실행했습니다.

바위 사이의 거리를 mid라고 하고, mid보다 간격이 좁으면 돌을 제거합니다. 그리고 나서 제거한 돌의 수를 이용해 바위 사이의 거리를 좁혀야 할 지 넓혀야 할 지 고르면 되겠습니다.

먼저 start, mid, end 변수를 만듭니다. start와 end는 초기에는 1과 distance가 되고, mid값은 start와 end값의 평균입니다.

그리고 제거한 돌의 수를 나타내는 변수인 cnt와 비교지점을 나타내는 변수인 prev를 만듭니다.

그 후에는 sort를 이용해 rocks를 정렬합니다. 순서대로 비교해야 정상적으로 거리를 구할 수 있기 때문이죠.

이제 while문을 만듭니다. while문이 돌아가는 조건은 start가 end보다 작거나 같은 경우입니다. 만약 start가 end보다 커지는 순간 while문이 종료되는 것이죠.

mid값을 (start+end)/2로 초기화합니다. cnt와 prev 역시 0으로 초기화합니다.

for문을 사용하여 출발지점부터 돌간 사이 간격을 확인합니다. 만약 mid보다 간격이 좁으면 제거하는 돌의 수를 1 증가시켜주고 (++cnt), 그렇지 않은 경우에는 prev에 현재 비교에 사용한 돌을 넣습니다. 이런 식으로 이전에 사용한 돌의 위치를 저장해놓아서 rocks를 건드리지 않고 손쉽게 이분탐색을 사용할 수 있습니다.

이 과정이 모두 끝나면, 마지막 distance와 마지막 돌과의 거리도 비교합니다. 만약 mid보다 distance - prev가 작으면 마지막 돌 역시 제거합니다.

이제 n과 cnt를 비교합니다. cnt가 n보다 크면 돌을 너무 많이 제거했다는 뜻이므로 end를 mid-1로 줄여줍니다. 거리의 최솟값을 줄여서 돌을 덜 제거하고자 하기 위함이죠. 만약 돌을 덜 제거했다면 start를 mid+1로 설정합니다. 그리고 만약 딱 맞게 돌을 제거했을 경우에도 start를 mid+1로 설정합니다. 이것은 최솟값중에 가장 큰 값을 찾아야 하기 때문입니다. start를 mid+1로 설정하면 돌 사이의 간격 한계가 더 커지기 때문에 같은 cnt임에도 가장 큰 값을 구할 수 있습니다.

그리고 n이 cnt보다 크거나 같은 경우 answer에다가 mid를 할당합니다. answer값은 반드시 cnt = n 조건에서 형성되어야하기 때문입니다.

그리고 while을 빠져나오게 되면 answer를 return하면 끝입니다!

2. 소스 코드

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

using namespace std;
/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: 이분탐색
    사용한 자료구조: vector
    
    논리 :
    바위 사이의 거리를 mid라고 하고, mid보다 간격이 좁으면 돌을 제거하는 형식으로 알고리즘을 짠다.
    start는 1, end는 distance가 되고 mid는 두 값의 평균으로 설정한다.
    그리고 몇개의 돌을 제거했는 지를 나타내는 변수인 cnt와 비교대상 돌 or 시작지점의 위치를 지정하는 변수인 prev를 만든다.
    rocks를 정렬한 후에 앞에서부터 간격을 잰다.
    
    입출력 예를 그대로 가져와서 알고리즘에 넣으면
    rocks가 [2,14,11,21,17], mid가 (1+25)/2 = 13 이라면 2-0 (idx 0 돌 제거), 11-0 (idx 1 돌 제거), 14-0, 17-14 (idx 3 돌 제거),
    21-14 (idx 4 돌 제거), 25-14 (마지막이기 때문에 남은 돌 1개도 제거) 이렇게 총 돌 5개가 제거된다.
    n은 2인데 5개를 제거했기 때문에 end = mid-1로 설정하고 다시 알고리즘을 반복한다.
    만약 n값보다 적은 돌을 제거했다면 start = mid+1로 설정하고 다시 알고리즘을 반복한다.
    만약 n값과 같은 돌을 제거했다면 거리의 최솟값 중 가장 큰 값을 구해야 하므로 start = mid+1로 설정한다.
    적거나 같은 돌을 제거했을 때 answer에 mid값을 넣는다.
    
    위 과정을 start > end가 될 때 까지 반복하고, answer을 반환한다.
*/

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    int start = 1;
    int end = distance;
    int mid;
    int cnt, prev;
    
    sort(rocks.begin(), rocks.end()); // 정렬
    
    while(start <= end){ // start가 end보다 커질 때까지 while문 반복
        mid = (start+end)/2;
        cnt = 0;
        prev = 0;
        
        for (int i = 0; i < rocks.size(); ++i){ // 출발지점부터 돌간 사이 간격 확인
            if(mid > rocks[i] - prev)
                ++cnt;
            else
                prev = rocks[i];
        }
        
        if(mid > distance - prev) // 추가로 마지막 돌과 도착지점 비교
            ++cnt;
        
        if(cnt > n) // 돌을 더 많이 제거했다면
            end = mid-1;
        else{ // 돌을 같거나 덜 제거했다면
            start = mid+1;
            answer = mid;
        }
    }
    return answer;
}

3. 후기

위에서도 말했지만, 한 눈에 보고 어떻게 해결해야 할 지 바로 파악하는 것은 저는 불가능했습니다. 약간의 검색의 도움을 받아 알고리즘을 이해할 수 있었습니다. (이것도 며칠 걸렸습니다..) 바로 파악하고 알고리즘을 작성하시는 수준이라면 아마 이 글을 검색해서 들어오지 않으셨겠죠..?

이분탐색이 참 간단해보이면서도 아이디어를 떠올리기 어렵고, 이 문제가 이분탐색 문제인지 발견하기 어려운 부분이 있습니다. 약간 힌트가 있다면 범위가 무지막지하게 크면 이분탐색일 가능성이 높다는 정도가 되겠군요.(하나씩 찾아서 10억번..은 시간이 너무 오래 걸릴 것이라는 것은 간단하게 떠올릴 수 있습니다.)

이제 마지막 테마인 그래프만 남았습니다. 불과 저번 학기에 들었던 자료구조 시간에 그래프를 간략하게 배웠었는데, 가볍게 복습하고 도전해야겠네요. 그렇다면 다음 포스팅에서 뵙겠습니다 :)

저작자표시

[프로그래머스 Level 4] [이분탐색] 징검다리 (C++)