🤔 왜 떠올리지 못했을까?
이 문제를 보고서는 쉽게 이분 탐색이라는 것이 떠오르지 않는다. 입력 값이 워낙 크니까 의심은 해볼 수 있지만 역시 방법은 쉽게 떠오르지 않았다.
심지어 이 문제는 1년전에 풀었던 문제였다..!(그 때도 못풀어서 답을 보긴 했지만) 그 때 당시에 풀지 못해서 대충 넘어갔던 것이 지금에 와서 큰 숙제로 다시 와버렸다... 매번 못풀은 문제들은 빠른 기간 내에 다시 풀어봐야 기억에 남고 풀이 방법이 기억을 쉽게 잊지 않는 것 같다. 다시 한번 당시의 나를 반성하며 앞으로는 이런 일이 없도록 기록도 열심히 하고 다시 풀어봐야 할 문제들 목록으로 저장해 놓고 다시 풀어봐야 겠다.
당시 기억으로는 풀다가 지쳐 거의 정답을 배껴 쓰기만 하고 전혀 이해하지 못하고 제출했던 것으로 기억한다. 사실 사람 수의 값이 작았다면 priorty queue로도 해결이 가능했겠지만, 전에 이렇게 정답 자체를 미지수로 두고 이분탐색을 해본 문제가 없었기 때문에 아이디어를 쉽게 떠올리지 못했다. 찾을 것이 무엇인지 모르는 상태에서 이분탐색이라니.. 비슷한 문제를 풀어보지 않았으면 떠올리기 힘든 아이디어인 것 같다.
2️⃣분 탐색 풀이법에 대한 고찰
결국 우리는 어떤 특정 인덱스나 값에 이분탐색을 하는 것이 아니라 정답 자체를 이분탐색을 통해 찾아가는 과정을 해야 한다. 우선 그 전에 알아야 할 가장 중요한 특성이 있다. 총 검사를 받아야 하는 사람의 수 (M) 는 입력 받은 값들에 대해서 (정답 X // 입국 심사 i, 걸리는 시간) 의 총 합이라는 점이다. 그렇기에 이분 탐색으로 답을 계속해서 찾아 나가는 과정을 거치는 것이다.
그렇기에 답을 엄청나게 큰 값과 0 사이를 두고 절반씩 나가면서 값들의 합을 찾아보는 과정이다.
답들 사이에서 하나씩 더해가면서 만약 더한 값들이 우리가 봐야하는 사람들의 수 보다 많다면 답을 절반으로 줄여서 찾아나가면 된다. 결국 총 O(logm * n)이라는 시간이 걸리게 된다.
좀 간단하게 케이스를 나누어서 설명하자면,
-
답은 0과 100000000000000이라는 엄청 큰 값 사이에 있다.
-
그래서 우리는 위의
사람의 수(M) == sum([(정답 // i) for time in 심사대]) 을 만족하는 정답을 찾아야 한다. -
만약 sum 의 값이 크다면 정답은 더 작은 곳에 위치한다는 의미이니 이분탐색처럼 오른쪽 구간을 중간으로 막아주고, 만약 sum이 더 작다면 왼쪽을 중간값을 넣어 해결한다.
😂 아 풀어본 문제도 못풀다니~
사실 이 문제를 다시 풀게 된 계기는 코딩테스트에서 다시 만났기 때문이었다.. 모 기업 코딩테스트에 문제로 나와서 기억이 나서 다시 풀었건만.. 당시 문제도 틀리게 풀었던 것으로 기억한다. 아마 코딩테스트는 입력값이 좀 작게 나와서 PQ로 풀면 맞게 풀렸겠지만, 당시에 PQ도 사용하지 않고 잘못된 풀이를 써 냈던 걸로 기억한다.
진짜 요즘 공부를 하면서 느끼는 것이지만 여러 문제를 많이 풀어보는 것보다 우선되는 것은 못푼 문제를 완벽히 이해하고 복기 할 수 있고, 최대한 이해하고 어떤 방법으로 풀었기 때문에 풀이 방법이 떠오르지 않았다는 것을 정리하는 게 중요하다는 생각이 많이 든다. 날을 잡고 풀었던 문제들을 싹 돌면서 디버깅 하듯이 바로 풀이가 떠오르지 않는 수상한 문제들을 다시 풀어봐야겠다.
참고로 이 문제를 풀었으면 바로
https://programmers.co.kr/learn/courses/30/lessons/64062
이 문제를 풀어보길 바란다.
