https://programmers.co.kr/learn/courses/30/lessons/43238
코딩테스트 연습 - 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한
programmers.co.kr
프로세스
- 걸리는 시간(제한 시간)을 기준으로 이분 탐색을 한다.
- 제한 시간 안에 총 몇 명을 심사할 수 있는지 확인한다.
- if (심사된 인원 >= 입국 인원) --> end = mid - 1 (최소 값을 구하기 위해)
- else --> start = mid + 1 (제한 시간이 짧아서 전부 검사할 수 없기 때문)
- 이분 탐색이 끝나면 start를 반환한다.
풀이
처음엔 우선순위 큐를 이용하는 방법을 시도했다. pq에서 뺄 때마다 지금까지 걸린 시간 += 검사 시간, 검사한 인원이 n보다 클 때까지 진행하는 방식이었다. 그런데 최악의 경우 시간 복잡도가 10억(명) * log(십만)이라 그런지 시간 초과가 났다.
이 문제는 대놓고 이분 탐색 카테고리에 있던 문제였어서 이분 탐색에 초점을 맞추고 접근해봤다.
뭘 기준으로 이분 탐색을 할 수 있을까..
경험상 직관적이지 않던 이분 탐색 문제들은 모두 정답이 될 것을 기준으로 두고 있었다. 그래서 걸리는 시간을 기준으로 생각해봤다. 시간을 정해놓고, 시간 안에 모든 인원을 심사할 수 있는지 확인하는 것이다.
제한 시간 안에 모두 심사할 수 있는지는 심사관마다 걸리는 시간을 제한 시간으로 나누면 구할 수 있다. 시간 복잡도는 O(심사관 수)이다.
/**
* 제한 시간 안에 모두 검사할 수 있는지 확인한다
* @param) time: 제한 시간
*/
fun isPossibleInTime(time: Long, officers: IntArray, numOfPeople: Int): Boolean {
var checkCount: Long = 0
for (checkTime in officers) {
checkCount += time / checkTime // 해당 심사관이 시간 안에 검사할 수 있는 인원 수
}
return if (checkCount >= numOfPeople) true else false
}이분 탐색의 범위
- 최소 시간: 심사관 수 >= 입국자 수, 각 심사관이 검사하는데 걸리는 시간 1분 -> 1분
- 최대 시간: 심사관 1명, 심사 시간 10억 분, 입국자 10억 명 -> 10억 * 10억 분
const val MAX_SIZE: Long = 1_000_000_000
...
var start: Long = 1
var end: Long = MAX_SIZE * MAX_SIZE탐색 범위 좁히기
걸리는 시간의 최소 값을 구하는 것이므로
- 시간 안에 모두 심사 가능 -> 더 짧은 시간에 대해 확인해보기 위해 end = mid - 1
- 불가능 -> 현재 시간이 너무 짧다는 의미이므로 start = mid + 1로 범위를 좁혀나간다.
그리고 이분 탐색이 종료됐을 때 start 값이 구하고자 하는 답이 된다.
코드
/* 걸린 시간을 기준으로 이분 탐색 */
import java.util.*
const val MAX_SIZE: Long = 1_000_000_000
class Solution {
fun solution(n: Int, times: IntArray): Long {
var start: Long = 1 // 심사관 >= 입국자, 검사 시간: 1분
var end: Long = MAX_SIZE * MAX_SIZE // 심사관: 1명, 검사 시간: 10억 분, 입국자: 10억 명
while(start <= end) {
val mid = (start + end) / 2
if (isPossibleInTime(mid, times, n)) {
end = mid - 1
} else {
start = mid + 1
}
}
return start
}
/**
* 제한 시간 안에 모두 검사할 수 있는지 확인한다
* @param) time: 제한 시간
*/
fun isPossibleInTime(time: Long, officers: IntArray, numOfPeople: Int): Boolean {
var checkCount: Long = 0
for (checkTime in officers) {
checkCount += time / checkTime // 해당 심사관이 시간 안에 검사할 수 있는 인원 수
}
return if (checkCount >= numOfPeople) true else false
}
}
'Problem Solving > 프로그래머스' 카테고리의 다른 글
| 프로그래머스: 보석 쇼핑 (Kotlin) (0) | 2022.04.16 |
|---|---|
| 프로그래머스: 메뉴 리뉴얼 (Kotlin) (0) | 2022.04.11 |
| 프로그래머스: 프린터 (Kotlin) (0) | 2022.03.31 |
| (Java) 프로그래머스 - 아이템 줍기 (0) | 2022.03.12 |
| [프로그래머스] 순위 (Kotlin) - 플로이드 와샬 사용하지 않고 풀기 (0) | 2022.02.14 |
