프로그래머스 코딩테스트 고득점 Kit - 이분탐색(입국심사, 징검다리)

1번 문제: 입국심사

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

풀이

n명이 입국심사를 위해 줄을 서서 기다리고 있고, 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다르다.
처음에 모든 심사대는 비어있으며, 한 심사대에서는 동시에 한 명만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있으며, 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해야 한다.

접근

이 문제에 어떻게 이분탐색을 적용해야 할지 고민이 많았다. 애초에 이 문제는 어떻게 풀어야 할까?

각 심사관이 한 명을 심사하는데 걸리는 시간은 모두 다르지만, 어떤 시간이 주어졌을 때 각 심사관이 그 시간동안 몇 명을 심사하는지는 알 수 있다. 어떤 시간동안 몇 명을 심사할 수 있는지 알아보고, 그 수가 n보다 크거나 같으면 가능한 시간인 것이다.

원래 이분탐색은 탐색하려는 값들에 대해 오름차순으로 정렬해줘야 한다. 하지만 이 문제에서 이분탐색으로 찾으려는 값은 n명을 검사하는데 필요한 시간이고, 주어진 배열은 각 심사관이 한 명을 검사하는데 걸리는 시간이므로 이 배열을 정렬해줄 필요는 없다.

먼저 n명을 모두 검사하는데 필요한 최대 시간을 구해야 한다. times 배열에 있는 값 중 최댓값을 찾아 n을 곱해준다. 여기서 max의 타입이 long인 이유는 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하이고, 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하라서 int 타입으로는 max의 값이 오버플로우될 수도 있기 때문이다. min은 모든 시간에 대해 탐색하기 위해 0부터 시작한다.

while문 안에서 min이 max보다 같거나 작을 때까지 mid값을 계산하고, mid라는 시간동안 심사를 마칠 수 있는 사람의 수를 의미하는 sum값을 계산한다. 이 sum값이 n보다 크거나 같다면 answer를 mid로 바꾸고, 더 작은 값이 될 수 있는지 알아보기 위해 max를 mid - 1로 바꾼다. sum이 n보다 작다면 mid보다 더 많은 시간이 필요한 것이기 때문에 min을 mid + 1로 바꾼다.

while문이 종료되면 이분탐색이 종료되고, n명을 심사하기 위한 최소 시간 answer가 구해졌기 때문에 이를 반환한다.

코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long max = 1000000000, min = 0;
        for (int time : times) {
            max = Math.min(max, time);
        }
        max *= n;
        long answer = 0;
        while (min <= max) {
            long mid = (max + min) / 2, sum = 0;
            for (int time : times) {
                sum += mid / time;
            }
            if (sum >= n) {
                max = mid - 1;
                answer = mid;
            } else {
                min = mid + 1;
            }
        }
        return answer;
    }
}

---

2번 문제: 징검다리

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

풀이

출발지점부터 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 함수를 작성해야 한다.

접근

이 문제에 어떻게 이분탐색을 적용해야 할까? 이분탐색은 보통 우리가 구하려는 값을 탐색할 때 사용한다. 이 문제에서 구하려는 값은 작게 보면 바위를 n개 제거한 뒤의 각 지점 사이의 거리의 최솟값이다. 그래서 이분탐색 로직에서 쓰일 mid값은 바위사이의 거리이므로, rocks 배열을 정렬한 뒤에 사용해야 한다.

2022년에 통과됐던 코드를 다시 제출해보니 틀렸다고 나오는데, 2023년 5월 15일에 추가된 테스트케이스에 대해 생각해볼 필요가 있다. 정확히 어떤 테스트케이스가 추가됐는지는 알 수 없어서 기존에 내 코드에 필요한 로직에 대해 고민해봤는데, 모든 바위를 확인한 뒤에 마지막 바위와 도착 지점과의 거리를 체크하지 않았었다. 기존의 코드가 종료된 이후에 이를 확인하는 것은 코드도 너무 지저분해지고, 불필요하다는 생각이 들었다. 그래서 주어진 rocks 배열의 뒤에 distance를 추가한 extendedRocks 배열을 만들었다.

max값은 도착지점을 의미하는 distance, min값은 출발지점을 의미하는 0으로 시작한다. while문 안에서 min이 max보다 같거나 작을 때까지 mid값을 계산하고, 거리를 비교할 앞의 돌의 위치인 rock은 시작지점을 의미하는 0, 제거한 돌의 개수를 의미하는 cnt는 0부터 시작한다. 여기서 mid는 언제나 최솟값이어야 하기 때문에 mid보다 각 지점 사이의 거리(extendedRock - rock)가 작은 경우의 수를 구한다. 이 경우에는 extendedRock을 제거하고, cnt에 1을 더한다. 거리가 mid보다 크거나 같다면 돌을 제거하지 않고 기준이 되는 비교할 돌(rock)을 extendedRock으로 변경한다.

여기서 extendedRock이 extendedRocks[extendedRocks.length - 1]일 경우가 문제인데, 이 값은 도착지점을 의미하는 distance이기 때문이다. 마지막이 extendedRock을 제거해야 하는 경우라면 도착 지점을 제거해야 한다는 의미인데, 이는 말이 되지 않는다. 하지만 이 문제에서는 제거해야할 돌의 위치를 반환해야 하는 문제가 아니기 때문에 이 경우만 앞의 돌을 제거한다는 의미로 사용된다. 이 부분은 로직적으로 문제가 있을 수도 있기 때문에 이는 추후에 테스트케이스가 더 추가된다면 통과하지 못 하게 될 수도 있을 것 같다.

아무튼 제거된 돌의 개수가 n보다 작거나 같다면 answer를 mid로 바꾸고, 더 작은 값이 될 수 있는지 알아보기 위해 max를 mid - 1로 바꾼다. cnt가 n보다 크다면 최솟값이 mid 이상인 경우로 만들기 위해 제거해야만 하는 돌의 개수가 n을 넘어간다는 의미이므로 더 큰 값을 탐색하기 위해 min을 mid + 1로 바꾼다.

cnt가 n과 정확히 같은지 확인할 필요는 없으며, while문이 종료된 이후에 answer를 반환한다.

코드

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int[] extendedRocks = Arrays.copyOf(rocks, rocks.length + 1);
        extendedRocks[rocks.length] = distance;
        Arrays.sort(extendedRocks);
        int answer = 0, max = distance, min = 0;
        while (min <= max) {
            int mid = (max + min) / 2;
            int rock = 0, cnt = 0;
            for (int extendedRock : extendedRocks) {
                if (extendedRock - rock < mid) {
                    cnt++;
                } else {
                    rock = extendedRock;
                }
            }
            if (cnt <= n) {
                min = mid + 1;
                answer = mid;
            } else {
                max = mid - 1;
            }
        }
        return answer;
    }
}

---

결론

이분탐색도 그렇게 자신있는 파트는 아니다. 애초에 이 알고리즘을 어떨 때에 써야하는지에 대한 생각이 잘 나지도 않을 뿐더러, 생각이 났다고 해도 중간중간에 실수할 수 있을만한 조건이 많은 문제가 대부분이기 때문이다.

그래도 일반적인 탐색 알고리즘이 O(N)의 시간 복잡도를 가진다면, 이분탐색 알고리즘은 O(logN)의 시간 복잡도를 갖기 때문에 잘만 사용한다면 더 효율적인 로직으로 문제를 해결할 수 있을 것이다. 더 많이 연습하고, 자신없는 알고리즘 파트도 자유롭게 다룰 수 있는 그런 사람이 될 수 있으면 좋겠다.