[리트코드][LeetCode][Easy][JAVA]35. 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.

You must write an algorithm with O(log n) runtime complexity.

 

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

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

 

 

---

 

분석

1. 중복되지 않은 정수의 정렬된 배열이 주어지고, 타겟 값이 주어진다.
   (1) 만약 그 타겟이 배열에서 발견되면 그 인덱스를 리턴하고,
   (2) 만약 배열 내에 없다면 타겟 값이 만약 정렬에 맞게 해당 배열에 삽입될 경우 들어갈 인덱스를 리턴한다.
2. 기본적으로 정렬된 배열이 주어지므로, 배열을 0번부터 순회하되 요소의 값이 타겟 값보다 커지면 해당 배열에 타겟 값이 없다고 봐야 함. 그 순간 loop를 멈추고 값이 존재하지 않을 경우에 대한 인덱스를 구하는 로직을 수행한다.

 

 

 

---

 

답안

class Solution {
    public int searchInsert(int[] nums, int target) {
        int answer = 0;
        
        int len = nums.length;
        for(int i = 0; i < len; i++) {
        	// 타겟이 발견되면 그 인덱스를 리턴
        	if(nums[i] == target) {
        		return i;
        	
        	// 타겟의 값보다 작으면 다음 loop를 계속 진행
        	}else if(nums[i] < target) {
        		continue;
        	
        	// 타겟의 값을 초과하면 인덱스를 리턴(타겟이 배열에 존재하지 않는 경우(1))
        	}else {
        		return i;
        	}
        }
        
        // 배열의 모든 요소보다 값이 큰 경우 마지막 인덱스로 들어가야 함. (타겟이 배열에 존재하지 않는 경우(2)) 
        return len;
    }
}

 

 

 

---

 

다른 사람의 답안

class Solution {
    public int searchInsert(int[] nums, int target) {

        int i ; 
        for(i = 0 ; i < nums.length && target > nums[i] ; i++){
            if(nums[i] ==  target){
                return i;
            }
        }
        return i;
        
        
    }
}

 

 

// int i 라는 변수를 loop 밖에서 정의하고 이용하는 방식.
// 내 코드보다 확실히 깔끔하다.

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

 

 

 

---

 

🔗링크