[백준] 1874번 스택 수열

문제

출처 : https://www.acmicpc.net/problem/1894

풀이과정

스택을 활용하는 문제이다. 처음에 문제를 읽었을 때 무슨 소리인지 몰라서 당황했다.

이 문제의 핵심은 1~n 까지는 무조건 스택에 들어간다는 것과 pop하는 조건을 잘 찾는 점인거 같다.

A를 1~n까지 저장하는 스택이라 하고, B를 입력된 수열을 저장하는 배열이라고 가정할 경우 A.pop()을 하는 조건은 다음과 같다.

1. A.top()과 B[i] 가 같을 경우 A.pop()을 통하여 입력된 수열을 만든다.

2. 이 과정은 스택이 비어있다면 진행하지 않는다.

소스코드를 보고 이해하는 게 더 빠를 거 같다.

소스코드

#include <iostream>
#include <stack>
#include <vector>
 
std::stack<int> stk;
std::vector<char> ans;
int input_seq[100001];
 
int main()
{
    std::cin.sync_with_stdio(false);
 
    int n, cnt = 1;
    std::cin >> n;
 
    // 수열 입력
    for (int i = 1; i <= n; i++)
    {
        std::cin >> input_seq[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        // 스택에 1~n 삽입
        stk.push(i);
        ans.push_back('+');
        // 스택이 비어있지 않을 때 스택의 top 원소가 입력 수열에 존재하면 pop 시킨다
        while (!stk.empty() && (stk.top() == input_seq[cnt]))
        {
            stk.pop();
            ans.push_back('-');
            cnt++;
        }
    }
 
    // 입력된 수열을 만들 수 있는 경우에는 항상 스택이 비어있다. 비어있지 않으면 만들 수 없는 경우이기 때문에 NO를 출력한다.
    if (!stk.empty()) std::cout << "NO\n";
    else
    {
        for (int i = 0; i < ans.size(); i++)
        {
            std::cout << ans[i] << "\n";
        }
    }
 
    
    return 0;
}