백준 탑 골드 5, 문제 특징 고려해서 풀어보기

 

https://www.acmicpc.net/problem/2493

해당 문제는 뒤에 있는 탑에서 앞에 있는 탑 중 자신과 가까운 제일 큰 탑을 찾는 문제이다.

위 그림을 토대로 정답을 보자면 다음과 같다.

0 0 2 2 4

나도 그랬고, 다른 사람도 다음과 같이 생각하지 않았을까? 

 1. 백준에서 스택을 활용하는 문제이니까, 스택을 어디다 쓰지? 어디다 쓸까?
  1-1. 스택의 특징이 무엇이지? FILO, LIFO이지?
 2. 반복문을 통해서 뒤에서 앞으로 이동하며 큰 탑을 찾아볼까?

 먼저 2번부터 본다면, 해당 입력 값의 크기가 N은 1 이상 500,000이하임으로 N^2 만 되도 약 10억번을 넘어간다는 사실을 알 수 있기에 이중 포문 이상으로는 사용하지 못한다. 그렇다면 해당 문제를 어떻게 풀어야 할까?

 위에서 이야기한 1번처럼 거의 Stack 문제임을 알고 왔기 때문에 Stack으로 풀어야겠다는 사고가 흘러가겠지만, 잠시 잊어보자.
 먼저 예시 데이터를 잘게 쪼개보자. 그렇다면 이상한 특징 하나가 보인다.

그 특징은 정렬이다. 정확하게는 큰  탑을 만날 때까지 정렬이 유지된다.

이러한 특징을 가진 데이터 구조를 단조 스택( Monotonic Stack )이라고 한다. 

단조 스택은 다음과 같다. ( 직접 읽으면 좋습니다.)

https://www.geeksforgeeks.org/introduction-to-monotonic-stack-2/

Introduction to Monotonic Stack - Data Structure and Algorithm Tutorials - GeeksforGeeks

단조 스택은 새로운 요소를 스택에 넣을 때마다 스택 내부의 요소를 정렬한다. NGE이란 Next Greater Element 문제에서 많이 사용된다. 다시 말하면 다음으로 큰 요소는 무엇인지 찾을 때 사용하는데, 위 문제도 돌이켜보면 NGE 문제임을 알 수 있다.

단어 뜻 => 단조: 값이 항상 일정한 방향으로만 변화함

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> heights(n);
    vector<int> answers(n);
    stack<pair<int, int>> s;

    for (int i = 0; i < n; ++i) {
        cin >> heights[i];

        while (!s.empty() && s.top().first <= heights[i]) {
            s.pop();
        }

        if (s.empty()) {
            answers[i] = 0;
        } else {
            answers[i] = s.top().second + 1; // 1-based index
        }

        s.push({heights[i], i});
    }

    for (int i = 0; i < n; ++i) {
        cout << answers[i] << " ";
    }

    return 0;
}