[백준] 2493번 탑

문제: 2493번: 탑

basic-algo-lecture/workbook/0x05.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x05.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n; // 탑의 수
    cin >> n;
    vector<int> answer;

    int prev = -1;
    // first: 높이, second: 인덱스
    stack<pair<int, int>> enableTops; // 왼쪽 오른쪽의 값이 자기보다 작은 탑들 저장
    for (int i = 0; i < n; i++) {
        bool flag = false;

        int cur;
        cin >> cur;

        pair<int, int> largerTop; // 자기보다 큰 탑 저장

        // enableTops 는 아래에 있는 요소가 위에 있는 요소의 값보다 작을수가 없음!!
        // 왜? 새로운 값을 넣으려고 할 때, 이 값보다 작은 요소들은 다 없애버리니까
        while (!enableTops.empty()) {
            pair<int, int> prev = enableTops.top();

            if (prev.first <= cur) {
                enableTops.pop();
            }
            else {
                flag = true; // 자기 보다 큰 걸 만나면 멈췅
                largerTop = prev;
                break;
            }
        }
        enableTops.push(make_pair(cur, i)); // 현재 값 넣어주기


        if (flag)
            answer.push_back(largerTop.second + 1); // 자신보다 큰 탑의 번호
        else
            answer.push_back(0); // 자신보다 큰 값이 없으면 0
    }

    for (int i = 0; i < n; i++)
        cout << answer[i] << " ";


    return 0;
}

 

1년 전에 못 풀었던 문제를 드디어 풀었다.

 

일단 이 문제를 해결할 수 있는 방법은 왼쪽에서부터 차례로 조건을 확인해가면서 스택을 이용하는 것이다.

 

처음에는 맨 오른쪽 요소가 top 에 있고, 그래서 뒤에서부터 값을 비교하면서 빼는식으로 하려고 했는데 이렇게 하면 시간 복잡도가 O(n^2) 이라 절대 문제를 해결할 수 없어보였다. 왜냐면 n 의 범위가 1부터 500,000 까진데 이거를 O(n^2) 으로 풀면 도저히 1.5초 만에 해결할 수 없기 때문이다.

 

그래서 다음에 생각한 건 맨 앞 요소부터 차례대로 스택에 넣어가면서 현재 스택에 넣으려는 값이랑 스택의 top 값이랑 비교했을 때, 현재 값이 더 크면 large 의 값을 현재 값으로 바꿔줄까였다. 왜냐면 이전 값이 현재 값보다 작으면 이전 값은 현재 값 다음으로 들어올 탑한테는 그냥 없는 것과 마찬가지라고 생각했기 때문이다.

 

근데 위와 같은 방법으로 하면 또 생기는 문제점이 현재 stack 의 값 중 무조건 가장 큰 값과 비교하기 때문에 현재 들어오는 값보다는 크지만 large 보다는 작아서 large 보다 더 가까이 있는 조건을 만족하는 탑이 존재하는 경우가 있을 때, 이를 체크를 못 하는 것이었다.

 

맨 앞 요소부터 차례대로 스택에 넣어가면서 연산을 수행하는 방식을 그대로 가져가되 다른 방식이 필요했다. 그래서 생각을 해봤는데 stack 에 수신 가능한 애들만 남겨놓는 식의 방식이 떠올랐다. 내가 생각한 수신 가능한 탑의 조건은 그냥 자기 뒤로 들어오는 값보다 크면 되는 것이었다. 앞에 자기보다 더 큰 값이 있는지는 상관없다. 그냥 내 뒤에 들어오려는 애가 나보다 작기만 하면 수신 가능한 탑이다.

 

그래서 특징을 발견했는데, 스택 요소는 top 으로 갈수록 값이 작아진다는 것이었다. 문제 풀고나서 봤더니 이걸 모노톤 스택이라고 하더라.. 새로운 걸 또 알게 되었다.

 

아무튼 그래서 현재 값보다 작은 top 들의 값을 스택에서 빼주고, 만약 큰 값이 있다면 거기서 while 을 끝내고 다음 for 문으로 넘어가는 식으로 구현했다.

 

사실 수식만 보면 for 문 안에 while 문이 있어서 시간 복잡도를 O(n^2) 으로 생각할 수 있지만 while 문에서는 현재 값보다 작은 값을 다 빼주고 있으므로 다음 for 문에선 뺀 값들을 마주할 수 없다. 그래서 n^2 이 될 수 없다. 사실 이거 마음으로는 받아들였는데 증명은 못하겠다;; 정리해놓은 글 있어서 좀 찾아왔는데 참고자료에 남겨놓으려고 한다.

 

아, 그리고 자신보다 큰 탑을 마주했을 때 그 탑의 번호를 쉽게 확인하기 위해서 stack 에 넣는 요소의 타입을 pair<int, int> 로 해줬다. first 요소는 탑의 높이, second 요소는 탑의 번호로 설정하니까 쉽게 할 수 있었다.

 

^~^ 1년 전과 비교했을 때 확실히 성장한 것 같긴 하다. 다행이다 ^_^ 더 열심히 해야겠다.

 

 

 

참고자료:

1. 모노톤 스택

모노톤 스택 Monotone Stack (JAVA)

모노톤 스택 Monotone Stack (JAVA)

 

2. 시간복잡도가 O(n^2) 이 아닌 걸 잘 설명한 글

[백준 2493번] 탑

[백준 2493번] 탑