설명을 읽다 보면 또리디인가 하는 생각이 들었다. 하지만 제한사항을 보는 순간 아 이건 무조건 선형 아니면 로그 복잡도를 가진 문제라는 게 보인다. 입국 심사를 기다리는 사람이 최대 10억 명까지 들어올 수 있기 때문에 복잡도가 제곱만 돼도 많이 어지럽기 때문이다. 백준에서는 제한 시간도 나와있기 때문에 대충 연산량과 시간을 비교해볼 수 있다. 하지만 프로그래머스는 백준과 달리 시간, 메모리 제약이 보이질 않는다. 그래도 어느 정도 합리적인 수준에서 알고리즘의 복잡도를 생각해보면 선형 시간도 어려울 것 같다. 그럼 남는 건 로그 시간이다. 로그 시간을 갖는 가장 대표적인 알고리즘으로는 이분 탐색이 있다.
이분 탐색은 [왼쪽, 오른쪽]의 범위를 정하고 범위의 절반씩 없애는 알고리즘이다. 이분 탐색 알고리즘을 사용하기 위해서는 어떤 숫자를 좌표로 사용할 지를 결정해야 한다. 이 문제에서 사용 가능한 좌표의 후보로는 처리 가능한 인원수와 걸리는 시간 정도가 있다. 하지만 처리 가능한 인원수를 좌표로 사용하기에는 첫 범위를 잡는 것부터 까다롭다. 실제로 이걸 사용해서 이분 탐색을 하기에는 어려워 보인다.
그래서 걸리는 시간을 사용한다. 첫번째 범위의 왼쪽은 가장 빠르게 모든 인원이 입국 심사를 받는 시간이다. 만약 모든 심사대가 1분씩 걸리고 심사 대보다 인원수가 적다면 모든 인원이 1분 만에 심사받을 수 있다. 따라서 왼쪽은 1이다. 그리고 오른쪽은 모든 사람이 가장 오래 걸리는 심사대에서만 가서 줄 서있는 경우다.
이렇게 첫 범위를 결정했다면 [왼쪽, 오른쪽]의 중간에서는 최대 몇 명의 사람이 심사를 받을 수 있는지 검사한다. 여기서 어쩔 수 없이 모든 심사대를 순회해야 한다. 최대로 심사 받을 수 있는 사람이 심사를 받아야 하는 인원수보다 적다면 왼쪽을 가운데로 끌고 온다. 그 반대의 상황이라면 오른쪽을 반대로 끌고 온다. 왼쪽과 오른쪽이 교차되는 순간에 알고리즘을 종료하면 된다.
처음 right를 할당할 때 long long으로 타입 변환하지 않으면 계속 오류를 만나게 된다. int의 최대 범위가 21억 정도 되기 때문인 것 같다. 아무리 생각해도 알고리즘의 문제가 없고 계속 한두개의 테스트에서만 자꾸 오류가 난다면 보통 타입에 문제가 있을 수 있다. 내가 사용하는 타입이 감당 가능한 값만 넣고 있는지 검사해보자.
'PS > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 여행경로 (C++) (0) | 2022.10.07 |
|---|---|
| [프로그래머스] 기지국 설치 (C++) (2) | 2022.10.06 |
| [프로그래머스] 숫자 게임 (2) | 2022.10.05 |
| [프로그래머스] 단속카메라 (0) | 2022.10.04 |
| [프로그래머스] 단어 변환 (0) | 2022.10.02 |