[C++] 뒤에 있는 큰 수 찾기 (프로그래머스 LEVEL 2)

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

---

문제풀이

우선 순위 큐를 사용해야 한다고 생각했다. numbers를 반복문을 돌며 우선순위 큐에 값이 들어 있으면 비교하여 numbers[idx]의 값이 클 경우 그것이 현재 우선순위 큐에 들어가 있는 값의 뒤큰수가 된다. 그리고 numbers[idx]값을 우선순위 큐에 넣어주도록 구현하였다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    priority_queue<pair<int, int>> pq;
    for(int i=0; i<numbers.size(); i++) {
        while(!pq.empty()) {
            int n = -pq.top().first;
            int idx = pq.top().second;
            
            if(n < numbers[i]) {
                pq.pop();
                answer[idx] = numbers[i];
            }
            else break;
        }
        pq.push({-numbers[i], i});
    }
    return answer;
}

다른 사람의 풀이를 보니 우선 순위 큐가 아니라 스택을 사용해도 풀 수있다. 왜 정렬하지 않아도 뒤큰수를 찾을 수 있는걸까?

로직을 돌면서 알아서 우선순위 큐 처럼 동작하여 뒤큰수를 구할 수 있기 때문이다.

[9, 1, 5, 3, 6, 2]

위 예제를 보자.

맨 처음 9가 스택에 들어간다.

9와 1을 비교한 뒤 스택에 들어있는 값이 더 크거나 같으므로 아무일도 일어나지 않고 1이 스택에 들어간다.

1과 5를 비교한 뒤 스택에 들어있는 값이 더 작으므로, 1을 스택에서 뺀다. 5가 스택에 들어간다.

이와 같은 반복을 하면, 자동으로 뒤큰수를 찾게 되는 것이다.

 

stack

9

9 1

9 5

 

스택의 맨 윗값이 현재 numbers[idx]에 있는 값보다 작을경우 빼버리므로 뒤큰수가 된다. 빠지지 않을 경우 그 다음 스택으로 들어오는 값은 반드시 현재 스택의 맨 위에 있는 값보다 작거나 같은 값이 된다! 그러므로 자동으로 우선순위 큐처럼 동작하게 되는 것이다.