백준 1874번 스택 수열 _ STACK (c++)

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

1874번: 스택 수열

 

이번에 다룰 1874번 문제는 앞선 포스팅에서 10828번의 스택을 구현할 때 만들어둔 스택 클래스를 그대로 가져다가 활용해서 풀 수 있는 문제이다.
아래 링크를 참조하면 된다.

2020/03/05 - [Programming/백준 문제풀이] - 백준 10828, 18258번 _ Stack과 Queue C++로 구현하기.

백준 10828, 18258번 _ Stack과 Queue C++로 구현하기.

 

그대로 스택을 구현하되, 이번에는 push가 있을 때마다 +를, pop이 있을 때마다 -를 호출하는 것이다.
하지만 이 문제에서 함정은 대체 어떤 수열이 주어지면 스택으로 해당 수열을 구현할 수 없는 지를 제대로 이해하는 것이다.
이것은 빈 종이를 하나 가져와서 일일이 그려보면서 이해하는 것이 제일 좋다.
4 3 6 8 7 5 2 1 이 보기로 주어졌다고 생각해보고 한번 구현해보자.
먼저 4를 호출하기 위해서 1 2 3 4를 push한 이후에 pop 을 해야 4가 나올 것이다.
그 후 3을 pop할 것이다.
그리고 6을 pop하기 위해서 5와 6을 push한 이후 6을 pop할 것이다.
이와 같은 관계를 한번 직접 표현해보면 다음과 같다. ㅁ 다홍 배경색은 pop한 수를 나타낸다
step1: 4 3 2 1
step2: 4 3 2 1
step3: 6 5 4 3 2 1
step4: 8 7 6 5 4 3 2 1

혹시 어떤 룰 같은 게 보이는가? 안 보인다면 이쯤 중간쯤 단계에서 5를 pop한다고 생각해보자. 가능한가??
위에 7에 가로막혀서 5나 2나 1을 pop할 수가 없다. 따라서 이럴경우 'NO'를 출력해야 한다!
그렇다면 이런 경우는 어떤 경우인가? 
위에서 보면 4->6이나 6->8처럼 값이 상승할때는 그만큼 그냥 push를 하면 되기때문에 아무런 에러를 유발하지 않음을 알 수 있다.
하지만 문제는 top에 위치한 수보다 작은 값을 호출할 때이다!

사실 이것만 파악했다면 이 문제는 다 푼 것이나 다름없다.
바로 코드를 보면 다음과 같다.

#include <iostream>
#include <string>
using namespace std;
#include <queue>

queue<char> answer;

class Stack{
private:
    const unsigned short stack_size;
    int* arr;
    int arr_size;
    int max;

public:
    Stack(int num): arr_size(0), stack_size(num+1), max(0) {arr = new int[stack_size];}
    void push(int n){
        arr_size += 1;
        if (stack_size == arr_size) cout << "PUSH: STACK IS FULL" << endl;
        else {
            arr[arr_size-1] = n;
            answer.push('+');
        }
        if (max<n) max=n;
    }
    void pop(){
        if (arr_size == 0) cout << "POP: STACK IS EMPTY" << endl;
        else {
            arr_size-=1;
            answer.push('-');
        }
    }
    int top() {
        if (arr_size == 0) return 0;
        else return arr[arr_size-1];
    }
    void size() {cout << arr_size << endl;}
    void empty() {
        if (arr_size == 0) cout << 1 << endl;
        else cout << 0 << endl;
    }
    int GetMax() {return max;}
    ~Stack() {delete []arr;}
};

int main(){
    int num;
    cin >> num;
    Stack stack(num);
    int input[num];
    for (int i=0; i<num; i++){
        cin >> input[i];
    }

    for (int i=0; i<num; i++){
        int top = stack.top();
        int max = stack.GetMax(); // 여태껏 스택에 들어온 값 중에 최댓값.
        if (top>input[i]){ // top이 들어온 값보다 크다면 NO
            cout << "NO";
            return 0;
        }
        if (top == input[i]) stack.pop();
        else if (max < input[i]){
            for (int j=0; j<input[i]-max; j++) stack.push(max+j+1);
            stack.pop();
        }
    }

    while(!answer.empty()){
        cout<<answer.front()<<"\n";
        answer.pop();
    }
    return 0;
}

 

끝!