참고
문제해설
NOTE
•
입력값 ⇒ 정렬된 정수 배열, 삽입해야 하는 정수 값
•
출력값 ⇒ 삽입되어야 하는 정수값의 idx 위치
문제 로직고민
NOTE
•
O(log n)을 요구하는 삽입위치 검색을 어떻게 구현하는가?
◦
O(log n)을 요구하는 검색의 경우 Binary Search가 대표적이다.
◦
left 와 right를 초기화하고 둘 값의 중앙 idx부터 비교를 시작한다.
◦
만약 해당 위치의 값보다 크다면, 우측 범위의 중앙값과 비교하러가고, left를 center값으로 초기화한다.
◦
만약 해당 위치의 값보다 작다면, 좌측 범위의 중앙값과 비교하러 가고, right를 center값으로 초기화한다.
◦
만약 해당 위치의 값과 동일하다면, 해당 idx를 반환한다.
◦
이 과정을 right-left가 0이 될때까지 반복한다. (실패)
•
left와 right의 길이가 2까지 줄어든다면, center값이 left나 right값으로 나오고, 무한반복을 돈다.
◦
재귀 조건을 바꾸는걸 고려해보았지만, 길이가 2인경우 넣을 위치를 구하는건 간단하다고 판단했다.
◦
right의 값보다 크다면, right+1위치에 넣어야 한다.
◦
left보다 크다면 left+1 위치에 넣어야 한다.
◦
이외에는 left위치에 넣으면된다.
작성코드
NOTE
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int center = (right+left)/2;
while(right - left > 1){
if(nums[center] > target) right = center;
else if(nums[center] < target) left = center;
else return center;
center = (right+left)/2;
System.out.println(left + " " + right);
}
return nums[right] < target ? right + 1
: nums[left] < target ? left + 1 : left;
}
}
Java
복사
정답코드
NOTE
class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length;
while (start < end) {
int ind = (start + end) / 2;
if (nums[ind] == target) return ind;
if (nums[ind] < target) {
start = ind + 1;
}
if (nums[ind] > target) {
end = ind;
}
System.gc();
}
return start;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
pointer를 움직일 때 start는 +1을 해주면, 위의 조건대로 코드가 더 깔끔해진다.
•
end의 경우에는 처음부터 nums.length-1이 아닌, nums.length를 했으므로, 따로 계산하지 않는다.
class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length - 1; // 수정된 부분
while (start <= end) { // 수정된 부분
int ind = (start + end) / 2;
if (nums[ind] == target) return ind;
if (nums[ind] < target) {
start = ind + 1; // 수정된 부분
} else {
end = ind - 1; // 수정된 부분
}
}
return start;
}
}
Java
복사
코드개선 (이런식으로 해야 내가 겪은 무한루프를 방지할 수 있다.)
처음 이진코드를 구현할때, 중앙값을 left나 right로 초기화 시켜줬는데, 이를 제외하고 해야 한다고한다.