[프로그래머스] 입국심사 (Java)

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

문제 정보

※ 자세한 문제에 대한 정보의 위의 링크를 참조해주세요!

제한 사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

문제 요약

해당 문제에서는 아래와 같이 말합니다.

🗨️ 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. **하지만** 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

처음에 해당 구문을 잘못 이해해서 무조건 빈 곳이 있으면 들어가야 한다고 생각을 했습니다. 하지만 여기서 요구하는 것은 아직 비지 않은 심사대가 있고 비어 있는 심사대가 있는 경우에 비어 있는 심사대에서 받는 것보다 비지 않은 심사대에서 받는 경우가 더 빠르게 끝나면 거기에서 받아야 하는 것입니다. 즉, 그냥 무조건 모든 사람이 심사를 제일 빠르게 받을 수 있는 최소 시간을 구하면 됩니다.

문제 풀이

위에서 본 문제에 대한 이해와 제한사항을 바탕으로 문제를 풀어봅시다. 처음 해당 문제를 봤을 때 저는 다음과 같은 생각이 들었습니다.

1. 제한 사항이 진짜 크다. → 완탐은 꿈도 못꾸겠네.
2. 최소 값 구하는 방법 → BFS, DP 등

이런 생각 후에 한 문제가 떠올랐는데 떡볶이 떡 자르기 문제라고 파라메트릭 서치를 이용하는 문제가 있습니다. 이게 떠올랐고 이분탐색 이용하면 시간도 괜찮을 것 같다는 생각이 들었습니다. O(Log (가능한 최대 시간) * (심사관의 수))의 시간 복잡도

파라메트릭 서치를 통해서 내가 구해야 하는 것이 뭘까는 문제에서 제가 구해야 하는 것과 동일합니다. **모든 입국하는 사람을 심사하는데 걸리는 최소 시간** 입니다.

그리고 이분탐색에서 범위를 어디로 줄일 것인지를 결정하기 위해서 조건이 필요한데 mid = (start + end) / 2 로 비교할 값을 정했다면 얘가 합당한 지를 봐야겠죠. 합당한지를 어떻게 알 수 있을까요?? mid는 시간인데 이 시간 안에 저 줄 서있는 사람들을 다 심사할 수 있다면 합당하니까 시간을 줄여볼 것이고 다 심사할 수 없으면 시간을 늘려야합니다.

그럼 시간 안에 사람들을 다 처리할 수 있을지를 어떻게 판별할까요?? 요기서 문제 조건이 빈 심사대에 무조건 가야한다는 조건이 있었다면 이 방식으로 못 풀었을 것 같은데 그거 상관없이 최소 시간이기 때문에 mid / (각 심사관이 심사하는데 걸리는 시간) 이런 방식으로 모든 심사관이 해당 시간안에 몇명을 심사할 수 있는지를 다 더하면 그 시간 안에 검사할 수 있는 총 인원이 나올 것이고 이게 n 값을 넘거나 같다면 처리가능, 그렇지 않다면 처리 불가능이라 생각하고 문제를 풀었습니다.

문제 코드

class Solution {

    private long result;

    public long solution(int n, int[] times) {
        long maxTime = (long)1000000000 * (long)1000000000;
        long minTime = 1;
        result = maxTime;
        search(times, n, minTime, maxTime);
        return result;
    }

    private void search(int[] times, int goal, long start, long end) {
        while(start <= end) {
            long mid = (start + end) / 2;

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

            if (goal <= timeCnt) {
                result = Math.min(result, mid);
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
    }
}