# 문제 원문
https://programmers.co.kr/learn/courses/30/lessons/43238
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
입출력 예
n / times/ return
6 | [7, 10] | 28 |
# 문제 풀이
입력 받은 n명을 times를 통해서 소요하는 시간을 구하는 문제이다. 이분 탐색 카테고리에 속해있으며, 기존 문제들이 단순히 배열상의 요소의 양방향 탐색이였다면 이건 해당 배열상의 요소를 임의의 가중치를 통해서 재가공한 후 탐색하는 응용을 해야한다. 이분탐색이라는 개념에 대해서 자세히 이해하고 있지 않다면 어려움을 느낄 문제로 보인다.
개인적으로는 어렴풋한 이해 정도로 알고 있던 내용을 찾아서 복습해야 할 필요가 있었다. 최대값과 최소 값 두 방향에서 탐색을 하고, n과 mid 값으로 구해진 인원수를 기준으로 범위가 조정 되는 점이 직관적이지 않아서 고생했다.
# 솔루션 플로우
1. 입력 받은 times 배열를 정렬시킨다.
2. 최소값 (left)를 0을 주고 최댓값(가장 큰수 * n)을 구한다.
3. 최소 시간이 최대 시간보다 커질때 까지 반복한다.
4. 두 지점의 중심(pivot || mid)을 (left + right) / 2 로 구한다.
5. 구해진 mid를 times 각 요소로 나누어서 해당 시간 동안 검사 하는 총 인원 수 (headCount)를 구한다.
6. 구해진 headCount 를 기준으로 인원이 많으면 최댓값 범위를 mid - 1로 주고, 적으면 최솟값을 mid + 1해준다.
7. 반복이 끝난 후 구해진 최소 소요 시간 left을 반환한다.
1. 이분탐색
function solution(n, times) {
times.sort((a, b) => a - b);
let left = 0;
let right = times[times.length - 1] * n;
while (left <= right) {
const mid = parseInt((left + right) / 2);
const headCount = times.reduce((result, current) => result + parseInt(mid / current), 0);
headCount >= n ?
right = mid - 1 :
left = mid + 1;
}
return left;
}
'개발 > 알고리즘' 카테고리의 다른 글
[프로그래머스][LEVEL3] 디스크 컨트롤러 (0) | 2022.02.10 |
---|---|
[프로그래머스][LEVEL3] 파괴되지 않은 건물 (0) | 2022.02.08 |
[프로그래머스][LEVEL3]N으로 표현 (0) | 2022.01.31 |
[프로그래머스][LEVEL2] 양궁대회 (0) | 2022.01.22 |
[프로그래머스][LEVEL2] 주차 요금 계산 (0) | 2022.01.18 |