[프로그래머스] 43238 - 입국심사 (Java, Python)

로고를 누르면 문제 페이지로 이동합니다.

---

 

문제 설명

n명이 한줄로 입국심사를 기다리고 있고, 각 입국심사대에서 한 명의 심사를 하는 데 걸리는 시간이 times 배열에 주어질 때 모든 사람이 심사를 받는 데 걸리는 최소 시간을 구하는 문제입니다.

제한사항

• 입국심사를 기다리는 사람(n)은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간(times 원소의 크기)은 1분 이상 1,000,000,000분 이하입니다.
• 심사관(times 배열의 길이)은 1명 이상 100,000명 이하입니다.

 

풀이

첫 번째 풀이

아이디어

우선순위 큐를 사용해 심사한 사람의 수를 하나씩 증가시키며 심사대에 배치해, n이 될 때까지 반복합니다.

코드 (Java)

결과 (Java)

입국심사를 기다리는 사람(n) 이 최대 1,000,000,000 명이기 때문에 O(n)의 시간복잡도로 풀이가 불가능했습니다.

 

두 번째 풀이

아이디어

아래 블로그의 풀이를 참고했습니다.

시간을 기준으로 해서, 시간의 최솟값과 최댓값을 이진탐색으로 조정해가며 모든 사람이 심사를 받는 데 걸리는 최솟값을 찾았습니다.

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

 

java로 풀 경우, maxTime(이진 탐색의 범위 중 큰 값)의 초깃값을 설정하는 부분에서 주의해야 합니다.

long 자료형으로 선언만 하면 times의 최댓값과 n이 모두 1,000,000,000 일 때, 1,000,000,000(int) 와 1,000,000,000(int) 의 곱이기 때문에 int의 범위를 벗어나 값이 깨진 상태로 maxTime 변수에 저장됩니다. 따라서 초기화해줄 때, 둘 중 하나의 값을 long 형으로 변환해 long 와 int 의 곱으로 만들어 값이 깨지지 않도록 해야합니다.

이진 탐색을 반복하는 과정에서 while문의 조건을 minTime < maxTime 로 두게 된다면, 찾으려는 값이 4일 때 아래와 같은 상황이 있기 때문에 답이 아니게 됩니다.

minTime	maxTime	midTime	time (구하려는 값)
1	5	3	3
4	4		4 < 4 가 아니기 때문에 더이상 탐색하지 않고 3 반환

코드 (Java)

결과 (Java)

왼쪽은 주석 처리된 부분 사용 X, 오른쪽은 주석 처리된 부분 사용 O

코드 (Python)

결과 (Python)

왼쪽은 주석 처리된 부분 사용 X, 오른쪽은 주석 처리된 부분 사용 O