[코딩연습] Search Insert Position 숫자를 넣을 자리 찾기

LeetCode 문제 중 난이도 Easy인 Search Insert Position이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

정렬되어 있는 배열과 목표값을 입력받아 목표값이 있는 위치의 인덱스를 구하여라. 목표값이 배열안에 존재하지 않을때에는 정렬 순서를 고려하여 목표값이 있어야할 위치의 인덱스를 구하여라.

Example 1

Input: [1,3,5,6], 5 ▶ Output: 2

Example 2 :

Input: [1,3,5,6], 2 ▶ Output: 1

Example 3: 

Input: [1,3,5,6], 7 ▶ Output: 4

Example 4:

Input: [1,3,5,6], 0 ▶ Output: 0

이 문제의 가장 쉬운 해결법은 배열을 처음부터 탐색하는 것이다. 목표값과 배열을 비교하여 배열의 값이 목표값보다 작을때는 넘어가다가 같거나 커지는 순간 해당 인덱스를 리턴한다. 배열을 전부 다 돌 때까지 리턴하지 않으면 배열에 저장된 모든 값이 목표값보다 작다는 뜻이므로 배열의 길이를 리턴하면 된다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i=0 ; i<nums.length ; i++){
            if(nums[i]>=target){
                return i;
            }
        }
        return nums.length;
    }
}

시간복잡도는 O(n), 공간복잡도는 O(1)로 나쁘지 않아 보이지만 이진탐색을 이용하여 속도를 좀 더 빠르게 개선 해보자.

이진탐색이라고 하니 왠지 엄청 복잡하고 어려울 것 같지만 우리는 이미 실생활에서 이진탐색을 쓰고 있다. 술자리에서 소주병 뚜껑에 있는 숫자를 맞추는 업앤다운 술게임을 생각해보자. 술래는 뚜껑에 써있는 숫자(1부터 50사이)를 사람들이 부르는 값과 비교해서 업인지 다운인지 알려준다. 한 명씩 돌아가면서 숫자를 부르고 한 바퀴 안에 숫자를 맞추면 술래가 술을 마신다. 이 때 숫자를 빨리 맞추고 싶다면 당연히 1부터 하나씩 비교하지 않는다. 맨 처음에 25를 부르면 업이냐 다운이냐에 따라 앞의 24개(1~24) 또는 뒤의 25개(26~50) 숫자들을 바로 제외할 수 있다. 이런식으로 남은 숫자들 중 중앙값을 부르고 반씩 버리면서 후보를 줄여 나간다.

이진탐색이 바로 그런 원리이다. 정렬되어 있는 배열에서 목표값을 찾기 위해 중앙의 값과 목표값을 비교한다. 코드로는 다음과 같다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int first = 0;
        int last = nums.length-1;
        
        while (first<=last) {
            int mid = (first+last)/2;
            if (nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                first=mid+1;
            } else {
                last=mid-1;
            }
        }
        return first;
    }
}

맨 처음에는 배열의 첫 인덱스인 0이 first이고 마지막 인덱스인 배열의길이-1이 last일 것이다. 중앙값(mid)을 구해 타겟값이 중간값과 일치하는지, 작거나 큰지 따져서 나머지 반을 버리고 또 중앙값을 찾는다. 이렇게 하면 시간복잡도를 O(log₂n)까지 줄일 수 있다. 마지막에 first가 last보다 크면 first를 리턴하는 부분은 배열에 목표값이 존재하지 않을 경우에 해당한다. 이 부분은 말로 설명하기보다는 직접 숫자를 넣어서 따져보는 것이 이해가 더 쉽다. 맨 위의 Example 2의 경우에 first, last, mid가 어떻게 바뀌는지 따져 보길 바란다.

참고로 int는 소수점이 있는 숫자는 소수점을 버림한다. 예를 들어 (2+5)/2는 3이 나온다.

문제 출처 - https://leetcode.com/problems/search-insert-position