백준 2493 탑 c++ ver.2

이미 4개월전에 푼 문제인데 뭔가 찝찝해서,, 발상이 좀 정형화(정형화? 간결함?) 될 필요가 있을거같다.

 

쉽게 생각해서 왼쪽부터 왼쪽에 자기보다 큰 애가 있으면 걔만 신경쓰면 된다. 큰애중 가장 가까운 애만!

그리고 출력은 그 가장 가까운 애의 인덱스 번호다! (문제에선 서로다른높이라고 명시했기에 같은높이는 경우가 없다.)

일단 왼쪽에 자기보다 큰 애가 있지 않을경우를 대비해서 가상의 엄청 큰 벽을 만들어준다.(인덱스 번호는 0)

pair로 묶어서 값의 인덱스를 추적하도록

100000001이 입력값 최대범위보다 1만큼 큰 값이기에 든든한 0번위치의 방벽이다.

 

자 그다음 모든 기둥은 자기보다 큰 바로직전의 벽 번호만 알면 된다.

1번 입력값은 무조건 방벽에 막혀서 0번인덱스를 출력한다.

자 2번타자가 들어올때 1번이 자기보다 작으면? 1번 그냥 삭제시켜도 된다. 왜냐, 그 후에 들어올 애들은 바로 자기보다 직전의 것이 자기보다만 크면 되기때문. 자기보다 큰 직전의 것 앞에 뭐가 있는지는 관심이 없다.

일종의 내림차순의 스택화.

 

그래서 입력값들을 넣을때마다 스택에서 입력값보다 작은건 다 삭제시켜주고 삭제되지 않은 최상단의 값을 출력한다.

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

int main(){

    ios::sync_with_stdio(0);

    cin.tie(0);

    int n;

    cin >> n;

    long long int temp;

    stack<pair<int, long long int>> s;

    s.push(make_pair(0,100000001));

    stack<int> last;

    for(int i = 1; i <= n; i++){

        cin >> temp;

        while(s.top().Y < temp){

            s.pop();

        }

        cout << s.top().X << " ";

        s.push(make_pair(i,temp));

    }

}