Python으로 배열에서 크기 k의 가장 경쟁력 있는 부분 수열 찾기

배열 nums와 값 k가 주어졌을 때, nums에서 크기가 k인 가장 경쟁력 있는 부분 수열(most competitive subsequence)을 찾아야 합니다.

여기서 부분 수열 s1이 같은 크기의 부분 수열 s2보다 더 경쟁력이 있다는 것은, 두 수열이 처음으로 서로 다른 위치에서 s1의 숫자가 s2의 해당 숫자보다 작다는 의미입니다.

예제 이해하기

입력이 nums = [4,6,3,7], k = 2라고 가정해 보겠습니다. 크기 2인 모든 부분 수열은 다음과 같습니다.

{[4,6], [4,3], [4,7], [6,3], [6,7], [3,7]}

이 중 첫 번째 원소가 가장 작은 [3,7]이 가장 경쟁력 있는 부분 수열이므로, 출력은 [3,7]이 됩니다.

풀이 접근 방식: 단조 스택(Monotonic Stack)

이 문제는 단조 증가 스택을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

원소를 순회하면서 현재 숫자가 스택의 최상단(top) 값보다 작고, 아직 제거할 수 있는 기회(attempts)가 남아 있다면 스택의 값을 제거(pop)합니다.
제거 가능한 횟수는 전체 길이에서 k를 뺀 값, 즉 len(nums) - k입니다. 최종 결과의 크기를 k로 유지하기 위해 필요한 만큼만 원소를 버릴 수 있습니다.

알고리즘 단계

attempts := len(nums) - k로 초기화합니다.
빈 리스트로 스택을 생성합니다.
nums의 각 숫자 num에 대해:
- 스택이 비어 있지 않고, num이 스택의 top보다 작으며, attempts > 0인 동안:
  - 스택에서 원소를 pop합니다.
  - attempts를 1 감소시킵니다.
- num을 스택에 push합니다.
스택의 앞에서부터 k개 원소를 반환합니다.

구현 예제

다음 Python 코드로 위 알고리즘을 구현할 수 있습니다.

def solve(nums, k):
    attempts = len(nums) - k
    stack = []
    for num in nums:
        while stack and num < stack[-1] and attempts > 0:
            stack.pop()
            attempts -= 1
        stack.append(num)

    return stack[:k]

nums = [4,6,3,7]
k = 2
print(solve(nums, k))

입력

[4,6,3,7], 2

출력

[3,7]

복잡도 분석

시간 복잡도: O(n) — 각 원소는 최대 한 번 push되고 한 번 pop됩니다.
공간 복잡도: O(n) — 스택에 최대 n개의 원소가 저장될 수 있습니다.

이 방법은 LeetCode 1673번 "Find the Most Competitive Subsequence" 문제와 동일한 유형으로, 단조 스택 패턴을 익히는 데 좋은 예제입니다.