[스택] 탑 (백준 24930)(C++)

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

2493번: 탑

 

1. 문제 개요

 

일직선 위에 N개의 서로 높이가 다른 탑이 있다. 각 탑의 꼭대기에서 왼쪽 방향으로 레이저 신호를 발사할 때, 발사한 탑의 높이보다 높은 높이를 가진 탑은 이를 수신할 수 있다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 있을때, 높이가 6, 9인 탑에서 발사한 레이저는 받을 수 있는 탑이 없다. 반면에 높이가 5, 7인 탑에서 발사된 레이저는 높이가 9인 탑에서 수신할 수 있다. 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는 지를 알아내라.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

높이가 각각 1, 2, 3, 4, 3, 2, 1인 7개의 탑이 있다고 할 때, 높이가 4인 탑의 왼쪽에 있는 탑들은 신호를 수신할 수 없게 된다.

높이가 3, 4인 탑이 나란히 있다고 할 때, 어차피 오른쪽에 있는 탑의 높이가 더 높기 때문에 앞으로도 3 이하의 높이를 가진 탑에서 발송한 레이저는 높이가 4인 탑에서 받기 때문이다.

 

이는 달리 말하면, 자신의 오른쪽에 위치한 탑이 자신보다 높이가 높으면, 해당 탑의 정보는 필요 없게 된다는 말이다.

이를 이용하면 stack을 사용해서 문제를 해결할 수 있다.

 

예시로 나온 6, 9, 5, 7, 4 다섯개의 탑을 이용해서 보면 다음과 같이 stack 이 사용될 것이다.

 

1. 6이 스택에 삽입된다. (6)

2. 두 번째 탑인 9의 높이가 6보다 크므로 6은 pop되고 9가 push 된다. (9)

3. 세 번째 탑의 높이 5는 9보다 작으므로 스택에 push 된다. (9, 5)

4. 네 번째 탑의 높이 7이 5보다 크므로 스택에 push 된다. (9, 5)

5. 마지막 탑의 높이 4가 5보다 작으므로 스택에 push 된다. (9, 5, 4)

 

이와 같은 정보를 사용하면 이 문제를 해결할 수 있다.

스택의 top index의 높이가 레이저를 발송하는 탑의 높이보다 높다면 해당 탑이 레이저를 송신하는 탑의 높이가 되며, 해당 탑의 정보도 스택에 push 해주면 된다.

스택의 top index가 높이가 레이저를 발송하는 탑의 높이보다 낮다면, stack에서 pop 되며, 해당 과정은 레이저를 발송하는 탑의 높이보다 높은 탑이 나올 때까지 반복된다.

 

처음에 문제를 잘못 읽어서 좌표압축으로 풀면서 많이 헤매다가 힌트를 읽고 겨우 풀었다...

 

 

4. 전체 코드

 

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>

using namespace std;

int main(void) {
    int N;
    stack<pair<int, int>> s;
    vector<int> v;
    scanf("%d",&N);
    
    for(int i=0;i<N;i++) {
        int temp;
        scanf("%d",&temp);
        int idx=0;
        while(s.size()>0) {
            pair<int,int> p = s.top();
            if(p.first<temp) {
                s.pop();
            } else {
                idx = p.second;
                s.push({temp,i+1});
                break;
            }
        }
        if(s.size()==0) s.push({temp,i+1});
        printf("%d ",idx);
    }
}

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!