[LeetCode] 5. Search Insert Position

Search Insert Position

link : leetcode.com/problems/search-insert-position/

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:

Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:

Input: nums = [1], target = 0
Output: 0

• target number의 인덱스를 찾고 만약 target넘버가 존재하지않으면 어디에 숫자가 들어가야할지 찾는 코드

• 예외의 경우가 계속해서 튀어나와서 정신없었다

class Solution {
    public int searchInsert(int[] nums, int target) {
        int idx = 0;

        //nums[0]보다 작거나 nums[nums.length-1]보다 큰경우
        // 즉 배열을 벗어나는 수인 경우를 제외해준다.
        if (target > nums[nums.length - 1]) {
            return nums.length;
        } else if (target < nums[0]) {
            return  0;
        }

        for (int i = 0; i < nums.length; i++) {
            //동일 값일 경우 i를 출력해야 하므로 break걸어줌
            if (target == nums[i]) {
                idx = i;
                break;
            } 

            //인덱스 사이의 값을 구해줌
            //단 i가 배열의 마지막 인덱스인 경우 i+!값이 존재하지 않으므로 제약 걸어줌
            if(nums[i] < target && target < nums[i + 1] && i != nums.length - 1){
                idx = i + 1;
                break;    
            }

        }

        return idx;

    }
}

수많은 오류를 뚫고 완성한 코드, 이 문제를 통해 예외처리와 반례에 대해 신중하게 생각해야겠다는 다짐을 하게되었습니다 ^&^

다른사람들은 어떻게 했나 봤는데 찾은 경악스러운 코드

class Solution {
    public int searchInsert(int[] nums, int target) {
        int i = 0;

        while (i < nums.length && nums[i] < target) i++;

        return i;
    }
}

난 10번이 넘는 시행착오를 통해 겨우 완성했것만 3줄로 깔끔하게 문제를 풀어버리는 클라쓰에 놀랐다

위의 코드는 O(n)이라서 나중에 데이터 값이 커지면 느려지게 된다.

결국엔 이진탐색의 최적의 방법이 된다.

이진 탐색의 경우 다른 글에서 포스팅해보겠다.