LeetCode 문제 풀어보기 - 35번 Search Insert Position프로그래밍 공부/코딩테스트 준비2022. 7. 16. 18:31
Table of Contents
각각의 정수로 정렬된 배열과 타겟 값이 주어지고,
배열안에 타겟 값이 있다면 그 인덱스를 리턴,
없다면 타겟값이 이 정렬된 배열에서 어디인덱스에 들어가야하는지 리턴해주면 된다.
이것도 O(log n) 시간복잡도를 가진 알고리즘을 사용해야 한다.
배열의 길이와 값의 제한이 있으며 nums배열은 오름차순, 별개의 값을 가진다.
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int MinIndex = 0;
int MaxIndex = nums.size()-1;
int half = 0;
while(MinIndex <= MaxIndex)
{
half = (MinIndex+MaxIndex) / 2;
if(nums[half] == target)
return half;
else if(nums[half] < target)
MinIndex = half+1;
else
MaxIndex = half-1;
}
return MinIndex;
}
};
이진검색 알고리즘 코드에서 실패했을때 리턴 값만 바꿔주었다.
이진검색 알고리즘으로 검색을했을때 값이 없다면 최소 인덱스와, 최대인덱스가 같아지는 상황이 나온다.
이 상황에서도 값이 안나온다면 찾는 값은 배열에 없는것이다.
이 최소 인덱스와 최대 인덱스가 같아졌을때 변수를 finalindex 라고 이름을 붙여 설명한다면
타겟과 finalindex 의 값을 비교했을때 타겟이 크면 최소인덱스 finalindex +1을 해주고 끝이난다.
그러면 finalindex의 다음 인덱스에 들어가야 하기 때문에 +1된 최소 인덱스를 리턴해주면 된다.
반대로 finalindex 보다 타겟이 더 작으면 최대 인덱스에 -1을 해주고 끝이난다.
그러면 최소 인덱스보다도 작다는 소리기때문에 최소 인덱스의 자리를 그대로 차지하면된다.
'프로그래밍 공부 > 코딩테스트 준비' 카테고리의 다른 글
#2 코테준비 - 연결리스트 (0) | 2022.09.22 |
---|---|
#1 코테 준비 - 배열 (0) | 2022.09.21 |
코테 준비하기 - 기본 사항들 (2) | 2022.09.21 |
LeetCode 문제 풀어보기 - 278번 First Bad Version (0) | 2022.07.22 |
LeetCode 문제 풀어보기 - 704번 Binary Search (0) | 2022.07.16 |
@데브준우 :: 개발초보 JW의 성장일기
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!