[백준 1874] 스택 수열 (C++/Python)

C++)

#include<iostream>
#include<stack>
using namespace std;
stack<int> st;
int arr[100002];

int main(void){
    cin.tie(0); cout.tie(0);
    ios_base :: sync_with_stdio(false);

    // cur = 입력받은 수열의 현재 위치
    int n, cur=0; string str;
    
    cin >> n;

    for(int i=0; i<n; i++)
        cin >> arr[i];

    // 숫자는 1부터 n까지 비교한다
    for(int j=1; j<=n; j++){
        // 만약 수열의 위치와 집어넣을 숫자가 같지 않다면 push
        if(arr[cur]!=j){
            st.push(j); 
            str += "+\n";
        } 
        // 같다면
        else {
            // 일단 넣고
            st.push(j); str += "+\n";
            
            // pop을 해준다 -> 현재 수열의 숫자와 스택의 맨 위의 숫자가 같지 않을 
            while(!st.empty() && (arr[cur]==st.top())){
                st.pop(); str += "-\n";
                cur++;
            }
        }
    }
    
    if(st.empty()) cout << str;
    else cout << "NO";
    
    return 0;
}

 

 

 

Python)

import sys
read = sys.stdin.readline

n = int(read().rstrip())
arr = []
ans = []
last = 1
flag = False

for _ in range(n):
    temp = int(read().rstrip())
    
    if not arr or (last <= temp):
        for i in range(last, temp + 1):
            arr.append(i)
            ans.append('+')
            last = i+1

    if arr[-1] == temp:
        ans.append('-')
        arr.pop()
    else:
        flag = True

if flag:
    print("NO")
else:
    print(*ans, sep='\n')