문제 개요
정렬된 배열과 하나의 목표 값(target)이 주어졌을 때, 해당 값이 배열에 존재한다면 그 인덱스를 찾아야 합니다. 만약 값이 존재하지 않는다면, 정렬 순서가 유지되도록 삽입했을 때의 인덱스를 반환해야 합니다.
예를 들어, 입력 배열이 [1, 3, 4, 6, 6]이고 target이 5라면 결과는 3이 됩니다. 인덱스 3에 5를 삽입하면 배열이 [1, 3, 4, 5, 6, 6]이 되어 정렬 상태가 유지되기 때문입니다.
접근 방법: 이진 탐색 활용
이 문제는 이진 탐색(Binary Search)을 활용하면 O(log n)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 탐색 범위를 절반씩 줄여가면서, target보다 큰 값이 처음 나타나는 위치(즉, 삽입해야 할 위치)를 추적하는 것입니다.
- n := 배열 A의 크기
- 만약 n < 1이라면 0을 반환합니다.
- low := 0, high := n - 1로 초기화합니다.
- low <= high인 동안 다음 과정을 반복합니다.
- mid := low + (high - low) / 2
- A[mid] == target이면 mid를 즉시 반환합니다.
- A[mid] > target이면 high := mid - 1, pos := mid로 갱신합니다.
- 그 외의 경우(A[mid] < target)에는 low := mid + 1, pos := mid + 1로 갱신합니다.
- 반복이 종료되면 pos를 반환합니다. 이 값이 target이 삽입되어야 할 인덱스입니다.
참고로 mid를 low + (high - low) / 2 형태로 계산하는 이유는 (low + high) / 2처럼 직접 더할 경우 발생할 수 있는 정수 오버플로를 방지하기 위함입니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int searchInsert(vector<int>& A, int target) {
int n = A.size();
if(n < 1) {
return 0;
}
int low = 0;
int high = n-1;
int mid;
int pos;
while(low <= high) {
mid = low + (high-low)/2;
if(A[mid] == target) {
return mid;
}
else if(A[mid] > target) {
high = mid - 1;
pos = mid;
}
else {
low = mid + 1;
pos = mid + 1;
}
}
return pos;
}
};
main(){
Solution ob;
vector<int> v = {1,3,4,6,6};
cout << (ob.searchInsert(v,5));
}실행 결과
입력:
{1,3,4,6,6}, 5
출력:
3
target인 5는 배열에 존재하지 않지만, 4와 6 사이에 삽입되어야 하므로 인덱스 3이 올바른 답이 됩니다. 만약 target이 배열에 이미 존재한다면 해당 인덱스가 그대로 반환됩니다.