문제 설명
숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 길이가 k인 부분 수열(subsequence) 중 사전순(lexicographically)으로 가장 작은 것을 찾아야 합니다.
예를 들어 nums = [2, 3, 1, 10, 3, 4], k = 3이 입력으로 주어지면 출력은 [1, 3, 4]가 됩니다.
해결 접근 방법
이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 결과 수열의 각 자리에 올 값을 왼쪽부터 차례대로 결정합니다.
- 결과의 j번째 원소는 이전에 선택한 위치 다음부터 시작하되, 뒤에 남은 (k − j − 1)개의 슬롯을 모두 채울 수 있도록 충분한 여유 범위 안에서만 선택할 수 있습니다.
- 각 단계에서 선택 가능한 범위 내의 최솟값을 고르면, 전체 수열이 사전순으로 가장 작아집니다.
구체적인 알고리즘 단계는 다음과 같습니다.
l := len(nums),r := k - 1로 초기화합니다.out := []빈 리스트를 준비합니다.- j를 0부터 k−1까지 반복하면서:
mn := nums[~r]로 후보값을 초기화합니다.- i를 r부터 l−1까지 반복하면서,
mn >= nums[~i]이면mn := nums[~i],l := i로 갱신합니다. r을 1 감소시킵니다.mn을out의 끝에 추가합니다.
- 모든 반복이 끝나면
out을 반환합니다.
여기서 주목할 점은 파이썬의 비트 연산자 ~(NOT)를 활용한 인덱싱입니다. 파이썬에서 ~i는 -(i + 1)과 같으므로, nums[~i]는 리스트의 뒤에서 (i + 1)번째 원소, 즉 실제 인덱스 n - 1 - i의 값을 의미합니다. 이 덕분에 유효한 선택 범위를 뒤에서 앞으로 훑으면서 최솟값과 다음 단계의 경계(l)를 동시에 추적할 수 있습니다.
파이썬 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, nums, k):
l, r = len(nums), k - 1
out = []
for j in range(k):
mn = nums[~r]
for i in range(r, l):
if mn >= nums[~i]:
mn = nums[~i]
l = i
r -= 1
out.append(mn)
return out
ob = Solution()
nums = [2, 3, 1, 10, 3, 4]
k = 3
print(ob.solve(nums, k))
입력
[2, 3, 1, 10, 3, 4], 3
출력
[1, 3, 4]
복잡도 분석
시간 복잡도는 각 자리마다 후보 범위를 선형 탐색하므로 O(n × k)이며, 공간 복잡도는 결과를 저장하기 위한 O(k)입니다. 참고로 단조 스택(monotonic stack)을 활용하면 O(n) 시간에 해결하는 최적화된 방법도 존재합니다.