[백준] 1874번 : 스택 수열

문제

 

---

풀이

 

 

스택과 만들어야할 수열이다. 스택에는 1~8까지 순서대로 들어올 것이다.

 

1 2 3 4를 순서대로 스택에 쌓다보니 수열의 첫번째 숫자인 4를 만났다. pop 해주자. 마침 그 다음이 3이니 한번 더 pop해주자.

 

다시 5부터 push하자.

 

6을 만나서 pop했다.

 

입력 예제 2번은 직접 해보시길 1 2 5까지만 만들어질 것이다.

---

소스코드

 

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

using namespace std;

void isStack(vector<int> arr) {
    int index = 1;
    stack<int> s;
    vector<char> pm;

    for (int i = 0; i < arr.size(); i++) {
        while (index <= arr[i]) { //arr[i]가 index보다 크거나 같으면 일단 push
            s.push(index);
            pm.push_back('+');
            index++;
        }
        if (!s.empty() && arr[i] == s.top()) { //empty 체크 중요함. 더 이상 push 못하는 상황에서 pop 가능한지 확인
            s.pop();
            pm.push_back('-');
        } else { //불가능하면 수열 만들 수 없음
            cout << "NO\n";
            return;
        }
    }
    for (int i = 0; i < pm.size(); i++)
        cout << pm[i] << '\n';
}

int main() {
    vector<int> arr;
    int n, input;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input;
        arr.push_back(input);
    }
    isStack(arr);
}

전체 소스코드다.

 

        while (index <= arr[i]) { //arr[i]가 index보다 크거나 같으면 일단 push
            s.push(index);
            pm.push_back('+');
            index++;
        }

n이 8일때 index는 1~8의 값을 갖는다. 앞서 4가 나올때까지 1, 2, 3, 4를 스택에 넣어주던 그 과정을 그대로 코드로 구현한 것이다.

 

        if (!s.empty() && arr[i] == s.top()) { //empty 체크 중요함. 더 이상 push 못하는 상황에서 pop 가능한지 확인
            s.pop();
            pm.push_back('-');
        } else { //불가능하면 수열 만들 수 없음
            cout << "NO\n";
            return;
        }

더이상 push가 불가능하다면(index>arr[i]) pop을 할 수 있는지 확인한다.

불가능하면 수열을 만들 수 없다는 것이니 NO를 출력하고 return한다.

 

    for (int i = 0; i < pm.size(); i++)
        cout << pm[i] << '\n';

무사히 끝까지 왔다면 수열을 만드는데 성공한 것이니 pm에 저장해둔 +와 -를 출력한다.