[BOJ][1874] 스택 수열

[ 오늘의 문제 한줄평 ]
string type은 max size가 정해져 있지 않다

스택 수열

로직은 틀리지 않았으나, string type variable의 maximum length를 생각하지 않아 발생한 참-사

string type variable의 maxiumu length는 str.max_size()가 반환한 값으로 정해진다

이는 컴퓨터 메모리에 따라 달라진다고 한다 (참고)

처음에 예제와 반례 모두 잘 나오는데 틀렸다고 나오길래 빡쳤는데 질문 게시판에서 영자님의 댓글 중 하나인 '답은 개행 문자를 제외하고 20만자가 넘을 수 있습니다'를 보고 ...? 설마설마 하다가 뒷통수 씨게 맞고 vector로 바꿈.

그리고 바로 맞음 ^_^...

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;

void print_lists(vector<int> _nums, stack<int> _tmps, int _point)
{
    cout << "remaining original vector" << endl;
    for (int i = _point; i < _nums.size(); i++)
        cout << _nums[i] << " ";
    cout << endl;
    cout << "remaining tmp stack" << endl;
    for (int i = 0; i < _tmps.size(); i++)
        cout << _nums[i] << " ";
    cout << endl;
}

int main()
{
    int n;
    cin >> n;

    vector<int> original_num; //1~n까지의 숫자를 오름차순으로 담고있는 벡터
    vector<int> target; //맞춰야할 수열
    stack<int> tmp; //수열을 만들 때 사용할 stack
    vector<string> ans; //정답 출력

    for (int i = 1; i < n + 1; i++)
        original_num.push_back(i);

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

    bool check = true;
    int point = 0; //original_num 벡터의 탐색 시작지점을 지정하는 변수 

    //target 수열의 앞부분부터 맞춰 나감
    for (int i = 0; i < n && check == true; i++)
    {
        // cout << "i = " << i << "\n\n";
        // cout << "now lists" << endl;
        // print_lists(original_num, tmp, point);

        //tmp stack의 top에 타겟 숫자가 있다면 tmp에서 pop하면 됨
        if (!tmp.empty() && tmp.top() == target[i])
        {
            tmp.pop();
            ans.push_back("-");
            // cout << "tmp pop" << endl;
            // print_lists(original_num, tmp, point);
        }
        //tmp stack의 top이 타겟 숫자가 아닐 때, 아직 tmp에 넣은 적이 없는 original_num 벡터에 타겟 숫자가 있는 경우
        // 타겟 숫자가 tmp stack의 top이 될 때 까지 tmp에 push하고 top이 되면 pop 하면 됨
        else if (!original_num.empty() && find(original_num.begin() + point, original_num.end(), target[i]) != original_num.end())
        {
            //tmp가 비었으면 일단 하나 넣고 시작
            if (tmp.empty())
            {
                tmp.push(original_num[point]);
                point++;
                ans.push_back("+");
                // cout << "tmp push" << endl;
                // print_lists(original_num, tmp, point);
            }
            //tmp의 top이 타겟 숫자가 될 때 까지 original_num의 숫자를 순서대로 넣음
            while (tmp.top() != target[i])
            {
                tmp.push(original_num[point]);
                point++;
                ans.push_back("+");
                // cout << "tmp push" << endl;
                // print_lists(original_num, tmp, point);
            }
            //tmp의 top에 타겟 숫자가 오면 pop함
            if (!tmp.empty() && tmp.top() == target[i])
                tmp.pop();
            ans.push_back("-");
            // cout << "tmp pop" << endl;
            // print_lists(original_num, tmp, point);
        }
        // tmp stack의 top이 타겟 숫자가 아님 && original_num에도 타겟 숫자가 없을 경우
        // 이건 tmp stack에 이미 타겟 숫자가 들어가 있다는 것. top이 아닌 이상 그 타겟 숫자를 먼저 pop 할 수 없으므로 수열 못 만듦
        else
        {
            check = false;
            ans.clear();
            ans.push_back("NO");
        }

        // cout << "\n\n";
    }

    for (int i = 0; i < ans.size();i++)
        cout << ans[i] << "\n";
}