[알고리즘]프로그래머스 43238번 - 입국심사

프로그래머스 43238번 - 입국심사

프로그래머스 43238번 - https://programmers.co.kr/learn/courses/30/lessons/43238

 

요구사항

1. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.

2. 모든 사람이 심사를 받는 데 걸리는 시간의 최솟값을 반환하라.

 

요구사항 분석 및  풀이과정

이 문제는 전형적인 최적화 문제입니다. 대부분 최적화 문제는 그냥 문제대로는 풀기가 어렵기 때문에 결정문제로 변경될 여지가 있는지 확인을 해봐야 합니다.

 

최적화 문제는 최솟값 중 최댓값, 최댓값 중 최솟값과 같은 유형의 문제를 말합니다.

결정 문제는 가능한지, 불가능한지 2가지로 결과가 정해지는 문제를 말합니다.

 

 

최적화 문제를 결정문제로 변경한 후, 결정 문제를 이분 탐색을 이용하여 해결하는 방법을

파라메트릭 서치(Parametric Search)라고 합니다.

 

1. 우리는 위 문제에서 구하고자 하는 걸리는 시간의 최솟값을 구하는 것이 아니라, 모든 사람이 특정 시간 t에 대하여 심사를 모두 받을 수 있는지, 없는지를 확인하면서 t의 범위를 줄여나가는 방법으로 걸리는 시간의 최솟값을 찾을 것입니다.

 

2. 여기서 중요한 점은 시간 t에 모든 사람이 심사를 받을 수 있다면 t 보다 큰 시간에도 자명하게 모든 사람이 심사를 받을 수 있습니다. 이러한 특성이 이분 탐색에서 빛을 발하게 됩니다. 그림을 통해 살펴보도록 하겠습니다.

 

 

3. 만약, 4초에 모든 사람이 심사를 받을 수 있다면, 5초, 6초,... 내에도 모든 사람이 심사를 받을 수 있습니다. 그 말은 4초에 모든 사람이 심사받을 수 없다면, 4초보다 작은 시간 내에도 불가능하다는 것을 의미합니다.

 

이러한 특성을 이분 탐색의 특성을 이용하면 탐색하여야 되는 범위를 매번 절반으로 줄여 O(lgN)에 원하는 결과를 도출할 수 있습니다.

 

이분 탐색을 적용하기 위해서는 반드시 탐색하려는 대상이 정렬이 되어있어야 합니다.

 

---

전체적인 흐름을 적어보면 다음과 같습니다.

 

결과로 가능한 시간의 최소와 최대를 기준을 이분 탐색을 진행하여, 절반에 해당하는 시간 t에서 모든 심사가 가능한지 검사합니다. 심사가 가능하다면 t 보다 긴 시간에도 모든 심사가 가능하므로 우측 절반을 버립니다. 

 

심사가 불가능하다면 t 보다 적은 시간에도 모든 심사가 불가능하므로 좌측 절반을 버립니다.

 

여기서 중요한 점은, 대부분 이렇게 쉬운 구현을 많이 실수한다는 것입니다. 구현을 위한 팁은 특정 조건을 만족하는 영역과 그렇지 않은 영역에 대해서 만족하는 불변 조건을 세우는 것입니다.

 

m의 좌측 영역은 주어진 조건을 만족하지 못하는 영역입니다. m의 우측 영역은 주어진 조건을 만족하는 영역입니다. l과 r은 항상 m을 기준으로 항상 한 칸은 벌어져있어야 탐색 범위가 주어진 조건을 만족하는 영역과 그렇지 않은 영역으로 나뉩니다.

 

이 문제에서는 결과로 가능한 시간의 최소는 1,  입국심사를 받는 사람은 최대 10^9 명, 각 심사관이 한 명을 심사하는데 걸리는 최대 시간은 10^9 시간, 심사관은 최소 1명에서 10^5 명이 하입니다.

 

가장 오래 걸리는 경우는 1명의 심사관이 한 명을 심사하는데 10^9 시간을 소요하는 경우이고, 이때 10^9  명을 심사하여야 한다면 총 10^18 시간이 걸리게 됩니다.

 

따라서 우리는 0시간부터 10^18 + 1 시간에 대하여 위의 방법대로 이분 탐색을 진행합니다.

---

여기서 그러면 중요한 점은 특정 시간 T에 대하여 모든 사람이 심사가 가능한지를 어떻게 파악하는지입니다.

 

이는 정말 간단합니다. 심사를 받는 사람 입장에서 생각을 하게 되면 어느 심사관에 가야 하는지, 다른 심사관이 심사 중인지를 생각하게 되어 머릿속이 복잡하게 됩니다.

 

하지만 심사를 하는 심사관 입장에서 생각하면, 자신은 한 사람을 심사하는데 정해진 시간(t)이 걸리며, 그 말은 특정 시간(l) 동안 자기가 심사할 수 인원은 정해져 있다는 의미입니다.

 

특정 시간 동안 심사관이 심사할 수 있는 사람의 수 = l / t

 

특정 시간 T에 대하여 모든 심사관이 심사할 수 있는 사람의 합이 심사를 받아야 하는 사람의 수보다 많다면, 시간 내에 모든 사람이 심사가 가능하다는 것을 의미합니다.

 

소스코드 작성

import java.util.Arrays;

class Solution43238 {

	private static boolean isPossibleTime(int[] times, int numOfPeople, long minTime) {
		long numOfPasser = 0;

		for (int time : times) {
			numOfPasser += (minTime / time);
		}

		return numOfPasser >= numOfPeople;
	}

	public long solution(int n, int[] times) {
		long l = 0;
		long r = (long)(1e18 + 1);

		Arrays.sort(times);

		while (l + 1 < r) {
			long m = (l + r) / 2;
			if (isPossibleTime(times, n, m)) {
				r = m;
			} else {
				l = m;
			}
		}

		return r;
	}
}

 

결과

 

소스코드 깃허브 주소

링크