정수 값들로 이루어진 배열과 길이 k가 주어졌을 때, 해당 길이를 가진 부분 배열(subarray) 중에서 가장 큰 것을 찾아야 합니다. 두 부분 배열을 왼쪽부터 인덱스별로 비교했을 때, 처음으로 값이 달라지는 위치 i에서 subarray1[i] > subarray2[i]라면 subarray1이 더 큰 부분 배열입니다. 쉽게 말해 사전순(lexicographic) 비교 기준이라고 생각하면 됩니다.
예를 들어 입력이 nums = [5, 3, 7, 9], k = 2라면, 만들 수 있는 부분 배열은 [5, 3], [3, 7], [7, 9] 세 가지입니다. 이 중 첫 번째 원소가 가장 큰 [7, 9]가 정답이 됩니다.
접근 방법
길이가 k인 부분 배열은 인덱스 0부터 len(nums) - k까지 어느 위치에서든 시작할 수 있습니다. 사전순 비교에서는 첫 번째 원소가 큰 쪽이 우선하므로, 시작 위치 후보 범위 안에서 값이 가장 큰 원소의 인덱스를 찾으면 됩니다. 만약 최댓값이 여러 곳에 있다면 더 오른쪽(뒤쪽)에 있는 위치를 선택해야 나머지 원소까지 비교했을 때 유리합니다. 오른쪽에서 왼쪽으로 탐색하면서 '엄격히 클 때만' 값을 갱신하면 자연스럽게 가장 오른쪽에 있는 최댓값이 선택됩니다.
알고리즘 단계
- start := len(nums) - k 로 초기화합니다.
- max_element := nums[start], max_index := start 로 초기화합니다.
- start가 0 이상인 동안 다음을 반복합니다.
- nums[start] > max_element이면 max_element := nums[start], max_index := start 로 갱신합니다.
- start를 1씩 감소시킵니다.
- 반복이 끝나면 nums[max_index : max_index + k]를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(k)입니다. (n은 배열의 전체 길이)
예제 구현
다음 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
def solve(nums, k):
start = len(nums) - k
max_element = nums[start]
max_index = start
while start >= 0:
if nums[start] > max_element:
max_element = nums[start]
max_index = start
start -= 1
return nums[max_index:max_index + k]
print(solve([5, 3, 7, 9], 2))입력
[5, 3, 7, 9], 2
출력
[7, 9]