1874.스택 수열

이 문제는 그렇게 어려운 문제는 아니였지만 굉장히 헷갈리긴 했다.

Stack과 Queue문제를 꽤 풀어본 것이 도움이 되었던 것 같다.

스택과 큐에 대한 다른문제들도 풀었지만 난이도가 너무 쉽다고 느껴 굳이 남기지 않았다.

하지만 처음에 문제를 거꾸로 이해해버렸고 반례를 만나서야 잘못 이해했다는 것을 알아챘다.

아직 반례를 생각해 내는 것이 굉장히 서툰 것 같다..

어쨌든 결과적으로 다 구현하고 나서 시간초과가 났는데 그러한 이유는 아래와 같다.

 

< Code 설명 >

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int main()
{
    queue<char>ans; // 부호정답이 저장될 queue
    queue<int> q;   // 입력받을 queue
    stack<int> t;   // 수열이 가능한지 쌓이는지 확인하는 stack

    int num;        // 수의 갯수
    cin >> num;     // 입력
    int tmp;        // 입력받기위함
    for(int i=0; i<num; i++){
        cin >> tmp; // 입력받아서
        q.push(tmp);// queue에 저장
    }
    for(int i=1; i<=num; i++){ // 1부터 num까지 순차적으로 넣음
        t.push(i);             // 스택에 넣고
        ans.push('+');         // 넣었다면면 정답 queue에 '+'도 같이 넣어줌
        if(q.front()==t.top()){ // 만약 넣던중 queue의 첫번째와 stack의 top이 같다면 
            while(!t.empty() && q.front()==t.top()){//stack의 top과 queue의 앞이
                                                 //같은게 있는지 계속 pop하며 확인
                t.pop();                         // 있다면 stack에서 pop으로 제거
                q.pop();                         // queue역시 pop해서 다음 것 확인
                ans.push('-');
            }
        }
        if(i==num && !q.empty()){  //끝까지 탐색이후에도 입력 queue가 비어있지 안다면
            while(!q.empty()){     
                t.push(q.front()); //나머지 queue값을 queue가 빌 때까지stack에 넣음
                ans.push('-');     //큐에서 빼서 스택에 넣으므로 '-'
                q.pop();           //다음 것도 넣어야하므로 pop
            }
        }
    }
    if(t.size()==q.size())    // 가능한 수열이라면 처음 입력받은 큐와 stack의 길이가 같음
        while(!ans.empty()){  // 부호 queue내용 출력
            cout << ans.front() << "\n";
            ans.pop();
        }
    else{                    // 비정상이라면 "NO"출력
        cout <<"NO\n";
    }

    return 0;
}

반드시 알아야할 TIP!!

15552번: 빠른 A+B

-> 절 때까먹지 말자!! 나는 C++을 쓰니까 되도록이면 "endl" 대신 "\n"'를 쓰는 걸 습관화 해야겠다.