[leetcode][1673] Find the Most Competitive Subsequence

문제 : leetcode.com/problems/find-the-most-competitive-subsequence/

---

부분 시퀀스들이 있을 때, 앞의 요소들부터 비교해나갔을 때, 사전 정렬과 비슷하게 가장 작은 수를 가지는 부분 시퀀스가 더 경쟁력 있다고 가정한다.

ex) [1,3,4,2], [1,3,5,3]는 앞에 두 요소는 동일한 값이고 세 번째 요소는 첫 번째 배열의 요소가 더 작기 때문에 (4 < 5) 첫 번째 배열이 두 번째 배열보다 더 경쟁력있다.

정수 배열 nums, 양의 정수 k가 주어졌을 때, 크기가 n인 nums 배열의 가장 경쟁적인 부분 시퀀스를 구해라.

 

---

stack을 사용한다.

nums배열의 i번째 요소인 num를 stack에 추가한다고 해보자.

 

1. num을 stack의 적절한 위치에 넣기 위한 사전작업 (pop)

stack의 위에서부터 탐색하며 nums[i]보다 큰 값들을 빼준다.

그런데 만들어지는 배열의 크기가 k를 만족시켜야 하므로 남은 요소들을 모두 stack에 추가한다고 했을 때에도 stack의 크기가 k 이상임을 만족해야한다.

해당 조건이 없다면 nums=[40,30,20,4], k=2인 경우 실제정답은 [20,4] 이지만 [4] 배열이 구해질 것이다.

즉, pop 하는 조건은. 스택이 비어있지 않고, top에 있는 수보다 num이 작으며, 스택크기 + 나머지 요소개수가 k 이상이 되는 경우이다.

 

2. num을 stack에 추가 or 추가하지 않기 (push)

사전 작업 후 stack 크기가 k보다 작다면 num을 stack에 push한다.

 

시간복잡도는 O(2N). 더 상세하게는 stack에 값이 들어가는 O(N) + stack에서 pop되는 O(N - k) = O(2N - k)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1673.%20Find%20the%20Most%20Competitive%20Subsequence.cpp

---

구현

설명에서는 stack 자료구조를 사용했다고 하였으나 소스코드를 보면 실제로는 deque를 사용했다.

반환타입이 vector인데 stl에서 제공하는 라이브러리는 stack 자료구조를 vector로 변환하는 것보다 deque 자료구조를 vector로 변환하는게 간편하기 때문이다.

참고 : [C++/STL] stack을 vector로 변환하기