문제 개요
주식의 일별 시세를 수집하고, 당일 주가의 스팬(span)을 반환하는 API를 만든다고 가정해 봅시다. 여기서 '오늘의 주가 스팬'은 다음과 같이 정의됩니다.
- 오늘부터 거슬러 올라가며, 주가가 오늘의 가격보다 작거나 같았던 연속된 날짜 수의 최댓값
예를 들어 7일간의 주가 기록이 [100, 80, 60, 70, 60, 75, 85]라면, 각 날짜의 스팬은 [1, 1, 1, 2, 1, 4, 6]이 됩니다. 이번 글에서는 이러한 동작을 수행하는 실제 모듈을 C++로 직접 구현해 보겠습니다.
접근 방법: 스택 활용하기
이 문제는 스택(stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 현재 가격보다 작거나 같은 과거 가격들은 더 이상 결과에 영향을 주지 않으므로, 스택에서 제거해도 된다는 점입니다. 알고리즘 단계는 다음과 같습니다.
- 두 개의 배열 st, v와 카운터 변수 counter를 선언하고, counter를 0으로 초기화합니다.
- next() 메서드가 호출되면 counter를 1 증가시킵니다.
- 스택이 비어 있지 않고, 현재 가격이 v[스택 최상단 요소]보다 크거나 같은 동안 스택에서 요소를 꺼냅니다(pop).
- 스택이 비어 있다면 ans = counter, 그렇지 않으면 ans = counter − 스택 최상단 값으로 설정합니다.
- 현재 가격을 v에 추가(push)합니다.
- counter 값을 st에 push합니다.
- ans를 반환합니다.
각 가격은 스택에 한 번 들어갔다가 한 번 나오므로, n번 호출 기준 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class StockSpanner {
public:
vector <int> st;
int counter;
vector <int> v;
StockSpanner() {
counter = 0;
}
int next(int price) {
counter++;
while(!st.empty() && price >= v[st.back() - 1])st.pop_back();
int ans = st.empty() ? counter : counter - st.back();
v.push_back(price);
st.push_back(counter);
return ans ;
}
};
main(){
StockSpanner ob;
cout <<(ob.next(100)) << endl;
cout <<(ob.next(80)) << endl;
cout <<(ob.next(60)) << endl;
cout <<(ob.next(70)) << endl;
cout <<(ob.next(60)) << endl;
cout <<(ob.next(75)) << endl;
cout <<(ob.next(85)) << endl;
}입력
클래스를 초기화한 후, 서로 다른 가격 값으로 next() 메서드를 순차적으로 호출합니다. 자세한 내용은 main() 함수를 참고하세요.
출력
1 1 1 2 1 4 6
동작 원리 살펴보기
입력 [100, 80, 60, 70, 60, 75, 85]를 순서대로 처리하면 다음과 같이 동작합니다.
- 100: 스택이 비어 있으므로 스팬은 1
- 80, 60: 앞의 가격이 더 크므로 각각 스팬 1
- 70: 바로 앞의 60보다 크므로 연속 2일 → 스팬 2
- 60: 앞의 70보다 작으므로 스팬 1
- 75: 60, 70, 60을 모두 포함하므로 스팬 4
- 85: 75까지의 모든 가격보다 크므로 스팬 6
이처럼 스택에는 '현재 가격보다 큰 가격'의 인덱스 정보만 남게 되어, 매 호출마다 불필요한 과거 데이터를 건너뛰고 빠르게 답을 계산할 수 있습니다.