[BOJ]1874번: 스택 수열(c++)

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

1874번: 스택 수열

 

 

#include <iostream>
#include <stack>
 
using namespace std;
 
int main()
{
    // 입출력 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    // 테스트 횟수 입력받고 버퍼 비우기 
    int n;
    cin >> n;
    cin.ignore();
 
 
    stack<int> s;
    // 메모리&속도 향상을 위해 vector가 아닌 char 배열 선언
    char answer[400001];    
    int a_i = 0;
 
    for (int i = 0, k = 1; i < n; i++)
    {
        // 한번에 하나의 숫자를 입력받고 버퍼 비우기
        int input;
        cin >> input;
        cin.ignore();
 
 
        // 스택이 비었거나, top이 input보다 작다면 --> top이 input과 같아질때까지 push
        if (s.empty() || s.top() < input)
        {
            while (k <= input)
            {
                s.push(k);
                k++;
                answer[a_i++] = '+';
                answer[a_i++] = '\n';
            }
        }
        // (스택이 비지 않고) top이 input보다 크다면 --> 불가능
        else if (s.top() > input)
        {
            break;
        }
 
 
        // 스택이 비지 않고, top이 input과 같다면 --> pop
        if (!s.empty() && s.top() == input)
        {
            s.pop();
            answer[a_i++] = '-';
            answer[a_i++] = '\n';
        }
    }
 
    // 문자열 끝 마무리
    answer[a_i] = '\0';
 
 
    // 스택이 비었다면 답안 출력, 아니라면 NO출력
    cout << ((s.empty()) ? answer : "NO");
 
    return 0;
}

 

 

TIP1

한번에 하나씩 입력값을 받고, 해당 숫자와 top을 비교하면 되는 문제!

처음엔 입력값을 모두 저장하도록 풀이해서 메모리 오버가 났다.

 

 

TIP2

stack.top() < input
stack.top() > input
stack.top() == input

3가지 경우의 수가 있다는 것을 중점으로 생각하기

 

 

TIP3

스택을 사용하지 않고, 배열만 사용한다면 더욱 빨라질 수 있다.