백준 - 탑(C++)

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

[

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

](https://www.acmicpc.net/problem/2493)

문제설명

단순 반복문을 사용한 구현문제로는 제약조건 때문에 시간초과가 날 수 있다. 1개의 for문을 사용하되 문제를 풀 수 있는 방법 하면 stack이 생각나야한다.

알고리즘

1. for문을 이용하여 앞에서 부터 스캔하며 stack에 값을 push한다.
2. 조건문안에 stack이 비었으면 자신보다 큰 탑이 없다는 것임으로 '0'을 출력한다.
3. stack의 top보다 크면 자신보다 큰 탑이 있는 것임으로 top의 인덱스를 출력한다.
4. 아닐경우 pop한다.

주의사항

1. stack을 생각하기 어려운 문제이다. stack만 생각한다면 풀기 쉬운문제이다.

구현

int main() {
    int N = 0;
    scanf("%d", &N);
    stack<pair<int,int>> s; //첫번째 값은 탑 높이, 두번째 값은 탑 인덱스
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &num[i]);
    }
    for (int i = 0; i < N; i++)
    {
        while(!s.empty())
        {
            if (s.top().first > num[i])
            {
                printf("%d ", s.top().second+1);
                break;
            }
            s.pop();
        }

        if(s.empty())
        {
            printf("0 ");
        }

        s.push({ num[i] ,i});
    }

}