[프로그래머스/Java] 입국심사(이분탐색 문제)

프로그래머스 알고리즘 고득점 Kit의 이분탐색 문제에 해당하는 '입국심사'를 자바로 풀어보았습니다. 

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

프로그래머스

 

문제 접근

 처음 이 문제를 접하고 들었던 생각은 어떻게 이 문제를 이분탐색으로 풀지?라는 것이었다. 내가 배워왔던 이분탐색과는 다른 느낌이었다. 하지만 '매개변수 탐색'이라는 개념을 접하고 나니 어떻게 이 문제를 풀어야 할지 알 수 있었다. 매개변수 탐색이란, 이분탐색을 이용해 최종답안에 가까워져 가는 탐색 방식을 말한다. 결국 '답이 될 결과'를 이분탐색하는 것이다.

 그래서 값이 될 수 있는 최솟값을 왼쪽 끝값으로, 최댓값을 오른쪽 끝값으로 두고, 이분탐색을 시행하면서 정답을 찾는 접근법으로 이 문제를 풀이해봤다.

 

 

---

문제 풀이 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {       
        // low, high, mid 설정
        Arrays.sort(times);
        long l = times[0], h = (long) times[times.length-1] * n;
        long m = (l + h) / 2;
        
        // 매개변수 이분탐색
        while (l < h) {
        	// 현재 탐색 중인 시간(m)에서 수용 가능한 n (avail_n) 계산
            long avail_n = 0;
            for (int t : times) {
                avail_n += (m / t);
            }
            
            // 이분탐색을 위한 h, l, m 재설정
            if (avail_n >= n) h = m;
            else l = m + 1;
            m = (l + h) / 2;
        }
        return m;
    }
}

 

 

---

시행착오 (주의할 점)

이 문제에서 내가 겪었던 시행착오는 아래 두 가지이다.

 

1. low와 high 설정 관련 문제

 여기서 주의할 점은 총 두 가지이다.

 (1) low를 high와 비슷한 "times[0] * n"으로 설정해서는 안된다.

 low를 n번 곱하는 것보다 다른 심사대를 적절하게 섞어 쓰는 것이 더 적은 시간의 결과를 낼 수 있는 것은 당연하다. (만약 low에 n명이 모두 가는 것이 최솟값이었다면, 이 문제의 답은 그냥 low*n이 될 것이다.) 따라서 low값은 0이나 최소 소요 시간을 가진 심사대 값 자체로 설정해 두는 것이 좋다.

 

(2) high 값을 구할 때 (long) 형 변환자를 꼭 써주어야 한다.

 만약 써주지 않는다면 high를 설정하면서 overflow가 발생하여 이상한 값이 high에 들어가 의도하지 않은 결과가 나올 수 있다.

long l = times[0], h = (long) times[times.length-1] * n;

 

 

2. high, mid, low 재설정 관련 문제

if (avail_n >= n) h = m;
else l = m + 1;

위 코드에서는 avail_n이 n 이상일 경우 h = m으로 설정한다. 이는 m이 유효한 답일 수 있으므로, m 값은 범위 내에 계속해서 포함하면서도 범위를 왼쪽으로 좁히기 위한 코드이다. 그런데 처음에는 아래 코드도 비슷하게 성립할 수 있다고 생각했다.

 

if (avail_n > n) h = m - 1;
else l = m;

 

 겉보기에는 비슷한 조건처럼 보이지만, 이 두 조건은 이진 탐색의 수렴 방식에서 중요한 차이를 만든다. 실제로 두 번째 방식은 일부 입력에서 무한 루프에 빠지는 문제가 발생했다.

그 이유는 m의 계산 방식 때문이다. m = (l + h) / 2는 정수 나눗셈이기 때문에 소수점 이하는 버려지며, 항상 l 쪽으로 치우친 값(floor 값)이 된다. 따라서 l = m을 하면 l이 변하지 않고 루프를 무한으로 돌면서도 계속 같은 값으로 초기화되는 상황이 발생할 수 있다. 예를 들면 아래와 같은 상황이 있다.

l = 3, h = 4
m = (3 + 4) / 2 = 3
l = m → l은 여전히 3 + h는 4 → 다음에도 m = 3 → 무한 반복

 

 비슷한 논리로 만약 Math.ceil()을 사용해서 m이 올림값이 되도록 한다면 반대로 두 번째 코드를 사용해야 무한 루프를 방지할 수 있을 것이다.