백준 - 2493 탑

[문제 링크]

스택을 이용하면 쉽게 푸는 문제이다.

나는 입력 받으면서 스택에서 체크하여 값을 출력하는 방식으로 풀었다.

값을 입력받으면, 스택을 체크한다. 스택을 체크해서 스택이 비었으면 그 탑 왼쪽에는 탑이 없는 것이므로 0을 출력한다.

탑이 있을 경우, 현재 입력받은 탑의 높이와, 스택의 top에 있는 탑의 높이를 비교한다. 만약 값의 크기가 현재 탑보다 작으면, 스택을 pop하여 다음 값을 다시 비교한다.

top에 저장된 높이 값이 현재 입력받은 높이값보다 같거나 클경우, 혹은 스택이 비었을 경우까지 이를 반복한다. top의 값이 같거나 클 경우에는 top의 인덱스를 출력하고, 비었으면 0을 출력한다.

그 다음에 현재 입력받은 값을 탑의 인덱스와 함께 스택에 push한다.

문제에 제시된 예제를 통해 예를 들어보겠다.

5
6 9 5 7 4

현재 스택은 비어있는 상태이다.

1. 먼저 6을 입력 받는다. 스택을 체크한다. 현재 스택에 삽입된 값은 없다, 콘솔에 '0'을 출력하고, 스택에 탑의 인덱스와 크기를 pair로 묶어 삽입한다.

출력 : 0

스택 : (1,6)

2. 그 다음 9를 입력받는다. 스택을 체크한다. top에 있는 값의 크기는 6이다. 현재 입력받는 9보다 작으므로 스택을 pop한다. 

출력 : 0

스택 :

그리고 다시 스택을 체크한다. 스택이 비어있다. 콘솔에 '0'을 출력하고, 입력받은 값을 삽입한다.

출력 : 0  0

스택 : (2,9)

3. 다음은 5이다. 스택을 체크한다. top에 있는 값은 9이고 현재 입력값보다 크다. top에 있는 인덱스를 출력하고 스택에 입력값을 push한다.

출력 : 0  0  2

스택 : (2,9)  (3,5)

4. 다음은 7이다. 스택을 체크한다. top에 있는 값은 5이고 현재 입력값보다 작다. 스택을 pop한다.

출력 : 0  0  2

스택 : (2,9)

그리고 다시 스택을 체크한다. top에 있는 높이 값은 9이다. 입력값인 7보다 크므로 top의 인덱스를 출력하고 스택에 push한다.

출력 : 0  0  2  2

스택 : (2,9)  (4,7)

5. 마지막으로 4이다. 스택 top을 체크하는데 top의 값은 7이고 입력값보다 크다. 인덱스를 출력하고 스택에 push한다.

출력 : 0  0  2  2  4

스택 : (2,9)  (4,7)  (5,4)

5번 반복했으므로 반복문이 끝나고 프로그램을 종료한다.

즉 스택에는 이전값중의 가장 큰 값과, 현재 값 사이에 있는 값들은 전부 없앤다고 보면 된다.

이를 구현한 코드는 다음과 같다.

#include <cstdio>
#include <stack>
#include <utility>
using namespace std;
int n, k;
stack<pair<int, int> > st;
int main() {
    scanf("%d", &n);
    for (int i = 1; i<=n; i++) {
        scanf("%d", &k);
        while (!st.empty()) {
            //스택의 top이 현재 입력값보다 크다면 신호 수신 가능이므로 
            if (st.top().second > k){
                //top의 위치를 출력하고 반복문을 탈출한다. 
                printf("%d ", st.top().first);
                break;
            }
            st.pop();
        }
        //스택이 비었으면 0을 출력한다. 
        if(st.empty()) printf("0 ");
        //그리고 현재 탑을 스택에 push 
        st.push(make_pair(i, k));
    }
}