[백준/c++] 2493번: 탑

 

 

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

2493번: 탑

 

 

N개의 높이가 다른 탑을 수평 직선의 왼->오 방향으로 세우고 레이저 송신기 서릴

한 탑에서 발사된 레이저 신호는 가장 먼저 만나는 하나의 탑에서만 수신 가능

6 9 5 7 4 왼쪽 방향으로 동시에 레이저 신호 발사

각 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지 알아내자

 

 

생각하는 게 좀 어려웠음.. 뭔가 히스토그램 같은 문제 같은데,, 어떻게 하면 좋을지..

일단 스택에 모든 원소를 넣지 말고,

- 현재 탑보다 스택의 top이 더 큰 경우, top의 인덱스 출력하고 현재 탑 스택에 넣기

- 현재 탑보다 스택의 top이 더 작은 경우, pop 하고 현재 탑 스택에 넣기

 

[A B] C

어차피 들어갈 탑(C)보다 스택에 있는 B가 크면 A가 B보다 더 커도 작아도 B에 막혀서 레이저가 오지 못함. B보다 작은 A는 pop 함

B가 A보다 크거나 작거나 뒤에 있는 애부터 C와 비교한다.

 

1. 비었으므로, 0 출력 - > 6 stack에 넣기 (6)

2. top보다 더 크므로 s.pop -> 비었으므로 9 stack에 넣기 (9)

3. top이 더 크므로 s.top(). first 출력 -> 5 넣기 (9 5)

4. top보다 더 크므로 s.pop -> (9 7)

5. top이 더 크므로 s.top().first 출력 -> 4 넣기 (9 7 4)

 

 

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    stack<pair<int, int>> s; //index, height
    int n, h;
    cin >> n;
    
    for(int i=1; i<=n; i++){
        cin >> h;
        while(!s.empty()){
            if(s.top().second > h){
                cout << s.top().first << ' ';
                break;
            }
            s.pop();
        }
        if(s.empty()) cout << "0 ";
        s.push({i, h});
    }
    return 0;
}

 

 

헷갈리는군..