[Swift] 프로그래머스 입국심사

 

Problem

 

코딩테스트 연습 - 입국심사

---

Solution

 

 

이번 문제는 이분탐색으로 풀어야하는 문제입니다.

 

1. 심사 시간 중 가장 심사가 오래 걸리는 시간과 모든 사람 숫자를 곱한 것으로 최댓값을 정한다.

 

가장 오래 걸리는 사람이 모든 사람을 맡았을 경우가 최대로 걸리는 시간이므로 위와 같이 최댓값을 정해줍니다.

 

만약 6명의 사람이 7분,10분 걸리는 심사관에게 심사를 받는다면 최댓값은 10분(가장 오래 걸리는 시간) * 6명 이므로

 

60분이 될 것입니다.

 

2.최대값을 각 심사 시간으로 나눠 총 심사받을 수 있는 시간을 구합니다.

 

1번에서 구한 최댓값을 각각 7과 10으로 나누면 8명,6명 이므로 14명입니다.

 

3. 심사를 받아야 할 사람이 모두 끝날 때 시간을 구해줍니다.

 

시작은 최소값 1분과 최댓값을 더한 뒤 2로 나눠준 중간값을 정해줍니다. 

 

예시로 하면 (1 + 60)/2 이므로 30이 될 것입니다.

 

만약 2번에서 구한값이 많거나 같다면 최소값을 중간값으로 바꿔주고 최대값은 중간값에 -1한 값으로 바꿔줍니다.

 

만약 2번에서 구한값이 더 적다면 최소값을 중간값에 +1한 값으로 바꿔줍니다.

 

이런식으로 심사를 받아야 할 사람 수가 될때까지 반복해줍니다.

 

예시로 하면 28분이 되었을때 6명의 사람이 되므로 28분을 반환해주면 됩니다.

---

Source Code

 

---

P.S

 

첫 풀이는 우선 times에 있는 값이 낮은 순으로 정렬한 뒤 1부터 n까지 사람을 탐색하면서 가장 낮은 수를 더해주면 최소값이

 

된다고 생각했다. 그리고 이분탐색 문제이기 때문에 가장 첫번째의 수가 몇 분걸리는지 더해준 뒤 정렬한 배열에 넣어주는

 

과정을 이분탐색으로 썼다. 그냥 잘못 접근해서 시간을 많이 버렸다.... 정말 처음 어떻게 사고하는냐가 중요한거같다.

---

Reference

 

[C++, Swift][프로그래머스] 입국심사