[백준/C++/Stack] 1874 - 스택 수열

1. 문제 링크

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

1874번: 스택 수열

 

2. 문제 해석

• input: 숫자 n, 그리고 n개의 숫자 (즉, 수열)
• output: push 일 때 '+', pop 일 때 '-', 불가능일때 'NO'
• LIFO 특성을 가진 stack 사용
• stack에 1부터 n까지 숫자가 있음. last in이 n.
• pop()된 숫자들은 max보다 이전에 입력으로 들어온 숫자들
• 입력을 배열에 저장하고, 값들을 비교하는 방법
• 입력 n번 반복
• 예제 입력 1 해석 
  • 입력1 = 4. 1,2,3,4 모두 push 한 후 4 pop
  • 입력2 = 3. 4까지 push 이미 했었기 때문에, 3 pop
  • 입력3 = 6. 5,6까지 push 한 후 6만 pop
  • 입력4 = 8. 7,8까지 push 한 후 8만 pop
  • 그 다음 입력들: 이미 max reach 했기 때문에, 남은건 모두 pop.
• 예제 입력 2 해석
  • 입력1 = 1. 1 push 한 후 1 pop
  • 입력2 = 2. 2 push 한 후 2 pop
  • 입력3 = 5. 3,4,5 push 한 후 5 pop
  • 입력4 = 3. 4부터 pop 해야 하기에 불가능. 'NO'
• 예제 입력 패턴
  • 입력이 한 번도 push되지 않은 숫자라면, 입력 숫자까지 push.
  • 만약 위에 있는 숫자 (stack.top()) 입력보다 크면, 'NO'
  • 그 외에는 입력이 뭐든 pop.

3. 발생한 문제

처음에 코드를 다 짜고 채점 했는데 출력 초과가 나와서 당황했다.

생겼던 문제는 'NO' 상황일 때, break문을 썼더니 그동안 push pop 했던 것들까지 cout 해버렸던 것이다.

NO 출력 이후에 바로 프로그램을 종료시키니 문제가 해결 되었다.

 

4. 코드

#include <iostream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

vector<char> answer;
stack<int> s;

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int i, n, input = 0;
    cin >> n;
    int count = 1;
    
    for (i = 0; i < n; i++){
        cin >> input;
        while (count <= input){
//            cout << "push\n";
            s.push(count);
            count++;
            answer.push_back('+');
        }
        if (s.top() != input || input > n){
            cout << "NO\n";
            return 0;
        } else {
//            cout << "pop\n";
            s.pop();
            answer.push_back('-');
        }
    }
    
    for (i = 0; i < answer.size(); i++){
        cout << answer[i] << "\n";
    }
    
    return 0;
}