정수로 이루어진 배열 A가 오름차순으로 정렬되어 있다고 가정해 봅시다. 이때 주어진 목표값(target)이 배열 안에서 처음 등장하는 위치와 마지막으로 등장하는 위치를 찾아야 합니다. 만약 목표값이 배열에 존재하지 않는다면 [-1, -1]을 반환하면 됩니다.
예를 들어 배열이 [2,2,2,3,4,4,4,4,5,5,6]이고 목표값이 4라면, 값 4는 인덱스 4부터 인덱스 7까지 연속해서 등장하므로 출력은 [4, 7]이 됩니다.
접근 방식: 두 번의 이분 탐색(Binary Search)
배열을 처음부터 끝까지 훑어보면 O(n)의 시간이 걸리지만, 배열이 이미 정렬되어 있다는 특성을 활용하면 이분 탐색을 두 번 수행하여 O(log n) 시간 안에 답을 구할 수 있습니다.
- 첫 번째 탐색: 목표값을 발견하더라도 멈추지 않고 왼쪽 절반을 계속 탐색하여 가장 왼쪽(첫 번째) 위치를 찾습니다.
- 두 번째 탐색: 첫 번째 위치 바로 다음 인덱스부터 다시 이분 탐색을 수행하여 가장 오른쪽(마지막) 위치를 찾습니다.
알고리즘 단계
- res := [-1, -1]로 초기화하고, low := 0, high := 배열 A의 길이로 설정합니다.
- low < high인 동안 아래 과정을 반복합니다.
- mid := low + (high − low) / 2 로 중간 인덱스를 계산합니다.
- A[mid]가 목표값과 같다면 → high := mid로 좁히고, res[0] = mid, res[1] = mid로 기록합니다.
- A[mid]가 목표값보다 작다면 → low := mid + 1, 그 외의 경우 → high := mid로 설정합니다.
- 탐색이 끝난 후에도 res[0]이 -1이면 목표값이 배열에 없다는 의미이므로 res를 그대로 반환합니다.
- 두 번째 탐색을 위해 low := res[0] + 1, high := 배열의 길이로 다시 설정합니다.
- low < high인 동안 아래 과정을 반복합니다.
- mid := low + (high − low) / 2 로 중간 인덱스를 계산합니다.
- A[mid]가 목표값과 같다면 → low := mid + 1로 이동하며 res[1] = mid를 갱신합니다.
- A[mid]가 목표값보다 작다면 → low := mid + 1, 크다면 → high := mid로 설정합니다.
- 최종 결과 res를 반환합니다.
예제 코드 (Python)
다음 구현을 통해 동작 방식을 더 자세히 이해할 수 있습니다.
class Solution(object):
def searchRange(self, nums, target):
res = [-1,-1]
low = 0
high = len(nums)
while low<high:
mid = int(low + (high-low)//2)
if nums[mid] == target:
high = mid
res[0]=mid
res[1]=mid
elif nums[mid]<target:
low = mid+1
else:
high = mid
if res[0] == -1:
return res
low = res[0]+1
high = len(nums)
while low<high:
mid = int(low + (high-low)//2)
if nums[mid] == target:
low = mid+1
res[1] = mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid
return res
ob1 = Solution()
print(ob1.searchRange([2,2,2,3,3,4,4,4,4,5,5,6], 4))
입력
[2,2,2,3,3,4,4,4,4,5,5,6] 4
출력
[5, 8]
복잡도 분석
이 풀이는 이분 탐색을 두 번 수행하므로 시간 복잡도는 O(log n)입니다. 추가적인 배열을 사용하지 않으므로 공간 복잡도는 O(1)로, 대규모 정렬 배열에서도 매우 효율적으로 동작합니다.