프로그래머스(입국심사, LV3)

문제 내용

문제 설명

입출력 예시 설명

---

제출한 코드

import java.util.*;

public class Solution {

    public static long solution(int n, int[] times) {
        long answer = 0;

        Arrays.sort(times);

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

        while (l <= r) {
            long mid = (l + r) / 2;

            long sum = 0;
            for (int time : times) {
                sum += mid / time;
            }

            if (sum < n) {
                l = mid + 1;
            } else {
                answer = mid;
                r = mid - 1;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        int n = 6;
        int[] times = {7, 10};

        // 28
        System.out.println(solution(n, times));
    }
}

---

후기

문제 요구사항에도 나와있듯이, 모든 사람을 빠르게 심사해야 했기 때문에 “심사받는 시간을 최소로” 만드는 것이라는 조건과, 추가적으로 한 심사대에는 동시에 한 명씩만 심사를 받을 수 있다 ” 와 “ 가장 빨리 비는 심사대로 가야 한다 ”는 조건들도 있었다

위의 여러 조건 중에서도 처음 한 명은 빈 심사대로 바로 이동하지만, 그 이후 사람들은 각 심사대의 처리 시간을 계산해 가장 빨리 끝나는 심사대를 선택해야하는 조건에서, 단순 반복문으로 for문을 돌려줘서 모든 시간을 탐색하면서 최소 시간을 찾는 것은 비효율적이라고 느꼈고 이분 탐색을 사용해 시간을 최적화해야겠다는 생각이 들었다

 

이분 탐색은 이전에 이산수학 과목을 공부하면서 가볍게 접했던 적이 있었었는데, 해당 문제에서의 적용은 심사 시간의 범위를 최소 시간 0분 ~ 최대 시간 으로 설정한 다음에, 가장 오래 걸리는 심사관 × n명 으로 잡고, mid 값을 기준으로 해당 시간 내에 모든 사람이 심사를 받을 수 있는지를 확인하는 방식으로 탐색 범위를 좁혔다. 이 과정에서 시간의 범위를 절반씩 줄여나가면서 최적의 시간을 찾아가는 것 으로 알고리즘을 설계하여 해당 문제를 풀이하게 되었다

 

이분 탐색에 대한 내용은 아래에서 다시 다루어보겠다

---

이분 탐색(Binary Search)

이분 탐색이란 ? 정렬되어 있는 범위에서 원하는 값을 찾기 위해 반씩 줄여가며 탐색하는 알고리즘으로, 
정렬이 되어 있다면 선형적으로 다 탐색할 필요 없이 범위가 반씩 줄어들기 때문에 시간복잡도가 O(log n) 이 나오게 되는 매우 효율적인 알고리즘이다

 

해당 문제에서는 먼저 mid 값을 현재 시간으로 설정한 뒤에, 각 심사관이 몇 명을 처리할 수 있는지 계산해주었다

while (l <= r) {
    long mid = (l + r) / 2; 
    long sum = 0;

    for (int time : times) {
        sum += mid / time;
    }

 

그리고 이어서 아래의 내용처럼 처리할 수 있는 인원이 n명보다 적으면 시간을 늘리고, n명 이상 처리할 수 있다면 시간을 줄이며 최소 시간을 찾는 방식으로 이분 탐색을 적용했다

    if (sum < n) {
        l = mid + 1;
    } 
    
    else {
        answer = mid;
        r = mid - 1;
    }

 

 

참고한 자료

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98