LeetCode 35. Search Insert Position

문제링크: leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

문제 요약: 정렬된 숫자배열(nums)와 숫자값(target)이 주어졌을때, target이 들어갈 index 위치를 구하시오.

 

문제 접근: 단순한 정렬문제이다. 시간복잡도 O(n)으로 풀었는데, 조건 잘 맞춰서 루프한번 돌면 끝낼 수 있다. 좀 더 효율적으로는, 배열이 정렬되어있기 때문에, 중간부터 탐색하면 O(logN) 으로도 풀 수도 있다. (binary search)

 

문제 풀이:

class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
        	// 배열의 현재 값이 target과 같으면 현재 index 반환.
            if (nums[i] == target) return i;
            // 배열의 현재 값이 target보다 크면 그전 index 반환.
            if (nums[i] > target) return i > 0 ? i-1 : 0;
            // 위 2개의 if문을 통과 했고, 다음 배열 값이 target보다 크거나 같다면, 현재 index 반환
            if (i < nums.length - 1 && nums[i+1] >= target) {
                return i+1;
            }
        }
		
        // for문이 끝났는데 여기까지 왔다는 경우는 맨 마지막 index
        return nums.length;
    }
}