[백준] 17298, 오큰수, Stack을 이용한 짝짓기 유형

YUN·2026년 3월 19일

C++

목록 보기

78/86

오른쪽에 위치한 수 중 처음으로 만나는 큰 수를 출력해야한다.
각 수마다 대응되는 오큰수를 찾는 문제, 즉 짝 짓기를 하는 유형이다.

사실 시간복잡도 조건만 없으면 이중 for문 O(N^2)돌리면 바로 풀리는 문제이다. 그러나 N<=100만이라 O(N^2)알고리즘은 시간 제한을 통과할 수 없다.

짝짓기 유형은 stack으로 푼다. 입력받은 수들을 stack에 push해뒀다가, 대응되는 오큰수를 찾으면 결과 배열 ret에 오큰수를 저장 및 stack에서 pop해준다.

이렇게하면 함수의 수행을 생각해봤을때 O(N)의 시간복잡도가 나온다. (stack에 n번 push 및 stack이 비지 않았을때만 pop하니까)

정답률이 되게 낮은데, 짝짓기는 stack으로 풀이한다는 거이 잘 떠오르지 않아서 그런 것 같다.

1. 풀이

#include <bits/stdc++.h>
    
using namespace std;

int n, a[1000004], ret[1000004];
stack<int> s;
int main()
{
    cin >> n;
    fill(&ret[0], &ret[0]+1000004, -1); //O(1)
    for(int i=0;i<n;i++) {//O(N)
        cin >> a[i];
        while(s.size() && a[i] > a[s.top()]) {
            ret[s.top()] = a[i]; //N번 실행*O(1) = O(N)
            s.pop(); //N번 실행 *O(1) = O(N)
        }
        s.push(i);// N번 실행 *O(1) = O(N)
        
    }
    for(int i=0;i<n;i++) cout << ret[i] << " ";
    return 0;
}

2. 오답노트

(1) 오큰수 찾기 = 짝짓기 유형임을 인지하지 못했다

오큰수 찾기를 짝짓기 유형으로 인지하지 못했다. 문제를보고, 이게 어떤 유형인지 매핑해보는 능력이 많이 부족한 것 같다.

문제에 직접적으로 짝짓기라는 언급이 없더라도, "어?이거 짝짓기 유형인가?" 하며 내가 알고있는 유형에 매핑해보는 것이 좋을 것 같다.

(2) 짝짓기는 stack으로 푼다.

짝짓기 문제는 stack으로 풀어야한다는 것을 잊어버렸다..잘 기억해둬야겠다.

(3) 시간복잡도 구하기

for(int i=0;i<n;i++) {//O(N)
        cin >> a[i];
        while(s.size() && a[i] > a[s.top()]) {
            ret[s.top()] = a[i]; //N번 실행*O(1) = O(N)
            s.pop(); //N번 실행 *O(1) = O(N)
        }
        s.push(i);// N번 실행 *O(1) = O(N)
        
    }

위 코드의 시간 복잡도가 O(N)인지 O(N^2)인지 헷갈렸다.

어찌됐건 시간 복잡도는 수행 횟수로 구한다.
s.push(i)는 총 n번 수행된다. s.pop() 은 s.size() 때문에 최대 n번 수행된다.

따라서 (반복문 고려해서) 빅 오 표기법으로 나타내면 둘다 O(n) 이므로, 위의 코드의 시간 복잡도는 O(n) 이다.