문제

• 문제 설명 : https://leetcode.com/problems/search-insert-position/

제출한 코드

class Solution {
    public int searchInsert(int[] nums, int target) {
        return searchInsert(0, nums.length - 1, nums, target);
    }

    private int searchInsert(int startIndex, int lastIndex, int[] nums, int target) {
        if (startIndex == lastIndex) {
            if (nums[startIndex] >= target) {
                return startIndex;
            } else {
                return startIndex + 1;
            }
        }
        if (lastIndex - startIndex == 1) {
            if (nums[startIndex] >= target) {
                return startIndex;
            } else if (nums[startIndex] < target && target <= nums[lastIndex]) {
                return lastIndex;
            } else {
                return lastIndex + 1;
            }
        }
        int insertIndex;
        int middleIndex = (startIndex + lastIndex + 1) / 2;
        if (nums[middleIndex] == target) {
            insertIndex = middleIndex;
        } else if (nums[middleIndex] > target) {
            insertIndex = searchInsert(startIndex, middleIndex, nums, target);
        } else {
            insertIndex = searchInsert(middleIndex, lastIndex, nums, target);
        }
        return insertIndex;
    }
}

잘한점

• 문제 풀이 방식은 바로 떠올랐음
• 문제를 끝까지 읽어 시간 복잡도 제한도 지킨듯
• 재귀 함수에 점점 더 익숙해 지는듯

개선할 점

• 끝마침 케이스를 잘 생각 해야 함 ( list의 length가 짝수일때, 홀수 일 때 )
• list의 길이가 짝수일 때, 중복된 숫자의 경우 케이스를 하나 빼먹은게 있었음 ( lastIndex )

Most Upvote Code

public int searchInsert(int[] A, int target) {
    int low = 0, high = A.length-1;
    while(low<=high){
        int mid = (low+high)/2;
        if(A[mid] == target) return mid;
        else if(A[mid] > target) high = mid-1;
        else low = mid+1;
    }
    return low;
}

배울 점

• 재귀를 활용하기보다, while문을 사용하는 경우가 좀 더 많은 것 같음
• 이렇게 짜면, 의미 없는 변수 / 함수들이 추가적으로 생기지 않음

Submission Image