오늘은 릿코드의 난이도 easy 문제 중 하나인 Search Insert Position 이라는 문제를 살펴보겠습니다. 이 문제는 정렬된 배열에서 찾으려는 수가 있는지 찾아보고, 있으면 그 수에 해당하는 index를, 없으면 주어진 수가 삽입되어야 할 index를 반환해야 합니다. 특히 이 문제에서는 알고리즘을 log n 의 시간 복잡도를 요구하고 있는데요, 아래 <사진 1>에서 제시되어 있는 문제의 예제를 하나씩 살펴보겠습니다.
첫번째 예제에서는 [1, 3, 5, 6] 이라는 배열에서 5라는 숫자가 있는지 먼저 검색합니다. 그러면 index 2에 숫자 5가 있네요. 그러면 5를 반환합니다. 두번째 예제에서는 [1, 3, 5, 6] 이라는 배열에서 2가 있는지 검색합니다. 그런데 배열에 2가 없네요. 그러면 2가 배열 안에 들어가야할 index를 검색합니다. 보니까 1 다음에 오면 되겠네요. 그러면 index 1이 반환됩니다. 세번째 예제에서도 배열은 [1, 3, 5, 6]이 주어졌는데요, 여기서 7이 있는지 검색합니다. 그런데 이번에도 7이 배열에 없네요. 그러면 6 다음에 7이 들어가야 하니까, index는 4가 되어야 합니다.
<사진 1> 출처: Leetcode "Search Insert Position"
이 문제에 대한 코드로, 우선 웹사이트의 도움을 받아 (?) 아래와 같이 코드를 작성해봤습니다. 우선 들어온 배열인 nums의 size가 0이면 그대로 0을 반환합니다. 왜냐하면 nums에 현재 어떤 숫자도 저장되어 있지 않기 때문이죠. 이후, algorithm 라이브러리의 lower_bound 함수를 사용해서, 현재 찾으려는 수와 같거나 큰 숫자가 있는 곳을 가리키는 iterator를 생성합니다. lower_bound 함수에 대한 자세한 설명은 C++ reference를 참조하셔도 좋습니다.
이후, 만약 iterator가 주어진 배열 nums의 맨 끝을 가리켰다면, 주어진 숫자가 nums의 맨 마지막 element로 삽입되어야 하는 것을 의미합니다. 따라서 이 때는 nums의 크기를 index로 반환합니다. 이에 해당되지 않는다면, distance 함수를 사용해서, it이 가리키고 있는 nums의 index를 반환합니다.
<사진 2> 출처: Leetcode "Search Insert Position"
이제 leetcode에 제일 많은 추천을 받은 코드를 살펴보겠습니다. 이 분이 작성한 코드도 저처럼 lower_bound를 사용했는데요, 다른 점은 저처럼 nums의 크기를 미리 체크하지 않고 있습니다. 그리고 lower_bound 함수를 적용한 결과를 if와 else로 구분할 필요 없이, 한 줄로 코드를 끝내고 있네요. 불필요한 코드를 추가하지 않았다는 점에서 이렇게 또 공부를 하게 됩니다.
<사진 3> 출처: Leetcode "Search Insert Position"
지금까지 릿코드의 "Search Insert Position"이라는 문제를 살펴보았는데요, 다음에도 또 다른 릿코드 문제를 들고 찾아뵙겠습니다 ^^
댓글