[백준] 2493 탑

문제 설명

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

2493번: 탑

n개의 탑이 서로 다른 높이를 가지로 있다.

탑은 수평 직선의 왼쪽 방향으로 레이저 신호를 발사하고, 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신할 수 있을 때, 각각의 탑에서 발사한 레이저 신호는 어느 탑에서 수신하는지 구하기

 

문제 풀이법

처음에는 굳이 stack을 써야 하나 싶었다

하지만 stack을 써야 하나씩 입력을 받으면서, 바로바로 값을 구할 수 있었다

 

stack<pair<int, int>> 형태의 stack을 선언한다

첫번째 인덱스는 탑의 높이, 두번째 인덱스는 탑의 번호를 담는다

 

주의 할점 은 비교할 것을 다 비교하고, 처리를 한 뒤에 push를 해야 한다

발사한 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하므로, 만나는 탑 뒤. 즉, 왼쪽에 있는 탑들은 쓸모가 없어진다

그래서 현재 탑의 크기와 스택에 있는 탑의 크기를 비교하면서 현재 탑의 크기보다 작은 원소들은 pop을 해준다

만일 현재 탑의 크기보다 스택에 있는 탑의 크기가 더 클 때, 그 탑의 인덱스를 출력한 후, 현재 탑에 대한 정보를 push 해준다

 

만일 스택이 비어있는 경우, 수신할 탑이 없다는 뜻이므로 0을 출력한다

 

주의 사항

cin, cout을 아예 사용하면 안된다

cin, cout을 쓰려면 밑에 코드를 작성한 후 사용하기

ios::sync_with_stdio(0);
cin.tie(0);

 

소스 코드

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    stack<pair<int, int>> s;
    
    for (int i = 0; i < n; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        
        while (!s.empty())
        {
            if (s.top().first < tmp)
                s.pop();
            else
            {
                printf("%d ", s.top().second);
                break;
            }
        }
        
        if (s.empty())
            printf("0 ");
        
        s.push({tmp, i + 1});
        
    }
    return 0;
}