1. 오늘의 문제

Search Insert Position

• 출처 : leetcode

2. 문제 분석

• nums : 중복되지 않은 정수가 정렬된 배열
• target : 정수
• 리턴값
  • target을 nums에서 찾을 수 있다면 인덱스 리턴
  • 찾을 수 없다면 nums에서 들어갈 인덱스 리턴

• 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

3. 문제 풀이

1. 이진 탐색으로 문제 풀이
2. left = 0, right = nums.length - 1로 설정
3. left <= right 동안 반복
4. mid = left + (right - left) / 2
5. 만약 mid 값이 target이랑 같다면 mid 리턴
6. mid 값 > target 이라면 right = mid - 1
7. mid 값 < target 이라면 left = mid + 1
8. target이 nums에 들어있지 않으면 들어갈 자리를 찾아야 하는데 탐색이 끝나고 나온 자리에 넣으면 됨 ⇾ left 리턴하면 됨

4. 구현 코드

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 이진 탐색으로 문제 풀이

        // left = 0, right = nums.length - 1로 설정
        int left = 0, right = nums.length - 1;

        // left <= right 동안 반복
        while (left <= right) {
            // mid = left + (right - left) / 2
            int mid = left + (right - left) / 2;
            // 만약 mid 값이 target이랑 같다면 mid 리턴
            if (nums[mid] == target) {
                return mid;
            // mid 값 < target 이라면 left = mid + 1
            } else if (nums[mid] < target) {
                left = mid + 1;
            // mid 값 > target 이라면 right = mid - 1
            } else {
                right = mid - 1;
            }
        }
        // target이 nums에 들어있지 않으면 들어갈 자리를 찾아야 하는데 탐색이 끝나고 나온 자리에 넣으면 됨
        // ⇾ left 리턴하면 됨
        return left;
    }
}

5. 오늘의 회고

• 22일차의 문제가 중복이 되는 문제였어서 새로운 문제가 나왔다. 그래서 풀어봤다.
• 이진 탐색을 연습할 수 있어 좋은 시간이었다.

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL