본문 바로가기

온라인 코딩/큐(Queue)와 스택(Stack)

[백준] 2493번 탑

 

 

문제

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define _CRT_SECURE_NO_WARNINGS
#include<stack>
#include<stdio.h>
 
using topPairData = std::pair<intint>//height, receive
 
int main() {
    int N{};
    scanf("%d",&N);
    std::stack<topPairData>tops;
    int currentHeight{};
    for (int i = 0; i < N; ++i) {
        topPairData pairData;
        scanf("%d"&pairData.second);
 
        pairData.first = i+1;
 
        while (tops.empty() == false) {
 
            auto top = tops.top();
 
            // 현재 탑보다 height가 크다면 0 출력
            if (top.second < pairData.second) {
                tops.pop();
            }
            //현재 탑이 더 크다면 수신
            else {
                printf("%d ",top.first);
                tops.push(pairData);
                break;
            }
        } //while end
 
        if (tops.empty()) {
            printf("0 ");
            tops.push(pairData);
        }
    }
}

후기

Stack을 이용해서 풀면 비교적 쉽게 풀 수 있는 문제이다. 하지만 이문제의 함정은 처음 구현의 방향을 잘못 잡으면 길을 헤맨다는 것이다.  정답 비율이 그것을 보여주는 느낌이다.

 

나는 처음에 문제에 있는 말대로 Stack에 모든 값을 넣고 오른쪽부터 하나씩 pop 하는 형식으로 문제를 풀었다. 이렇게 하다 보니 중간에 따로 N번 반복문을 돌아야 하는 구간이 생기기도 하고 따로 예외 구분도 많아져서 통과하지 못했다.

 

그래서 생각을 바꿔서 처음에 Stack에 넣을 때 현재 top(스택 최상단)값 보다 값이 작다면 수신을 하고 아니라면 pop 해서 만날 때까지 돌게 하였다. 

 

이렇게 다시 보면 결국 이것도 N-1번 정도 복잡도가 생겨서 처음에 구현한거랑 비슷하다고 보는데 테스트 케이스를 통과한 거 보면 이쪽이 좀 더 정답에 가까운 방법이었던 거 같다. 

 

std::cout, cin 으로는 통과하지 못해서 printf와 scanf을 사용했다.

 

 

출처 및 레퍼런스

문제 링크: https://www.acmicpc.net/problem/2493