백준 1874 (스택 수열) c++

문제

1874번: 스택 수열

1 ~ n 으로 이루어진 수열이 주어지면 

1부터 n 까지 차례대로 스택에 넣어 push와 pop을 통해 주어진 수열을 만들 수 있는지 확인하는 문제 입니다.

주어진 수열을 만들 수 있으면 push할 때마다 '+'를 출력하고 pop할 때 마다 '-'를 출력합니다.

만약 주어진 수열을 만들 수 없으면 NO를 출력하고 종료합니다.

 

정상적으로 주어진 수열을 만들 수 있으면 구현하는데에는 문제가 없었습니다.

하지만 주어진 수열을 만들 수 없을 때를 잘 살펴보아야 합니다.

저는 처음에 수열이 주어지면 1부터 n까지 수를 스택에 쌓으므로 

주어진 수열에 n이 나온 이후로는 무조건 내림차순으로 수열이 진행되어야 주어진 수열을 만들 수 있다고 생각

했습니다.

따라서 처음에 제가 작성한 코드는 아래와 같습니다.

int n;
cin >> n;
for (int i = 0; i < n; i++)cin >> arr[i];
bool check = false;
bool confirm = false;
for (int i = 0; i < n; i++) {
    if (check && arr[i - 1] < arr[i]) {
        confirm = true;
        break;
    }
    if (arr[i] == n)
        check = true;
}
if (confirm) {
    cout << "NO";
        
}

수열을 살펴보면서 수열에 n이 등장하면 check변수를 true로 바꾸고 이후로는 내림차순으로 진행되면 주어진

수열을 만들 수 있는 것이고 그렇지 않으면 NO를 출력해주고 끝내면 되는 것입니다.

 

하지만 문제에 나와있는 예제는 모두 맞았지만 

33%에서 출력초과가 나오면서 틀렸습니다.

질문게시판에 나온 반례도 그대로 나왔지만 문제점을 찾을 수 없었습니다.

제가 처음에 작성한 코드입니다.

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)cin >> arr[i];
 
    bool check = false;
    bool confirm = false;
    for (int i = 0; i < n; i++) {
        if (check && arr[i - 1] < arr[i]) {
            confirm = true;
            break;
        }
        if (arr[i] == n)
            check = true;
    }
    if (confirm) {
        cout << "NO";
        
    }
    else {
        int a = 1;
        for (int i = 0; i < n; i++) {
            int key = arr[i];
            while (1) {
                if (st.empty()) {
                    cout << '+' << '\n';
                    st.push(a);
                    a++;
                }
                if (st.top() == key) {
                    cout << '-' << '\n';
                    st.pop();
                    break;
                }
                st.push(a);
                cout << '+' << '\n';
                a++;
            }
        }
    }

 

구글에서 다른 사람들이 작성한 code를 살펴보니 

주어진 수열에서 NO를 출력하는 조건이 제가 작성한 것과는 달랐습니다.

먼저 제가 출력초과를 받았다는 것은 NO를 판별하는 조건이 틀렸다는 것이었습니다.

 

다른 분들이 한것을 보니 주어진 수열를 실제로 stack를 사용해 push와 pop을 통해 진행하면서 

push와 pop을 할 때 vector<char> 에 다가 '+' 나 '-'를 넣어주어 마지막에 한번에 출력하는 방식을

사용하였습니다.

NO나 나오는 경우에는 stack에 마지막 까지 원소가 있는 경우에만 NO나 출력됩니다.

위와 같이 짧게 끝나는 것을 알 수 있습니다.

 

여러 방식으로 구현하는 방법을 떠올려야 합니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[100001];
stack<int>st;
vector<char>c;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)cin >> arr[i];
    int a = 0;
    for (int i = 1; i <= n; i++) {
        st.push(i);
        c.push_back('+');
        while (!st.empty() && st.top() == arr[a]) {
            st.pop();
            c.push_back('-');
            a++;
        }
    }
    if (!st.empty())cout << "NO" << '\n';
    else
        for (int i = 0; i < c.size(); i++)cout << c[i] << '\n';
    
    return 0;
}