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

1. 서론

최근에 이진탐색 방식으로 풀었던 문제가 생각나서 도전했다.

 

2. 문제 설명

 

3. 나의 풀이

나의 코드

위의 문제를 푸는 방법에서 아쉬웠던 점은, 처음에는 배열을 생성하여 문제를 풀려고 했었다. 전혀 그럴 필요가 없었는데 이진탐색은 배열에서 이용한다는 생각이 있었어서 그런지 문제 해결을 위한 배열을 생성했다. 배열을 생성하는 과정에서 중첩 반복문으로 배열안의 원소를 채우다보니 타임아웃이 발생했다. 이를 어떻게 해결할지 고민하던 중, 질문 란에서 어떤 분의 right 에 숫자를 넣는다는 얘기를 듣고 그대로 차용했더니 통과되었다. 코드에서 한줄만 변경한 것이지만 문제 푸는 아이디어의 가장 큰 부분을 도움을 받아 문제를 푼 것이라 스스로 풀지 못해 너무 아쉽다.

 

4. 다른 사람의 풀이

나의 방식과의 차이점은 times 리스트를 정렬하여 가장 right 값에 times 리스트의 가장 마지막 값에 n을 곱한 값을 삽입했다는 것이다. 그 외의 부분은 유사하다.

 

5. 결론

이진 탐색은 left, right가 항상 배열의 위치를 의미하지는 않을 때도 있다.

이진 탐색을 이용하는 문제는 어떻게 이진 탐색을 적용해야 할지가 제일 중요한 것 같다. -> 이 부분은 문제를 계속 풀어보면서 익혀나가는 것이 중요해 보인다.