BOJ - 1874 - 스택 수열

ggh·2022년 5월 11일

boj cpp ps stack

백준

목록 보기

13/112

BOJ - 1874 - 스택 수열

문제

1874번: 스택 수열

문제 개념

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.
- n = 8
  - 기준 수열 : [ 1 2 3 4 5 6 7 8 ]
스택에 push하는 순서는 반드시 오름차순을 지킨다.
- 엇갈리면 안된다.
임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다.
- 임의의 수열 : [ 4 3 6 8 7 5 2 1 ]
  - 계산결과 : + + + +, - -, + +, -, + +, - - - - -

구현 - vector 사용

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

int main()
{
    int num;
    vector<int> OrderStack;     // 입력스택 
    vector<int> NumQueue;       // 기준 큐
    stack<int> TmpStack;        // 임시스택
    vector<string> answer;      // 정답스택
    
    cin >> num;
    for(int i=1; i <= num; i++)
    {
        int tmp; 
        cin >> tmp;
        // 4 3 6 8 7 5 2 1
        OrderStack.push_back(tmp);
        // 1 2 3 4 5 6 7 8 
        NumQueue.push_back(i);
    }
    for(int i=0; i < OrderStack.size(); i++)
    {   
        while(1)
        {   // 스택의 상단과 인풋값이 맞을때 까지 
            if(TmpStack.empty() || TmpStack.top() != OrderStack[i])
            {
                TmpStack.push(NumQueue[0]);
                if(!NumQueue.empty())
                    NumQueue.erase(NumQueue.begin());
                else
                    break;
                answer.push_back("+");  
            }   
            else if(TmpStack.top() == OrderStack[i])
            {
                TmpStack.pop();
                answer.push_back("-");
                break;
            }       
        } 
    }
    
    if(!TmpStack.empty())
    {
        answer.clear();
        answer.push_back("NO");
    }
    for(auto el : answer)
        cout << el << '\n'; 
}

구현 - stack queue lib 사용

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std; 
// 입력 저장 스택 
// 기본 N까지의 수열스택
// 임시로 담아둘 스택 
// 정답에 입력할 스택  

int main()
{
    int num;
    queue<int> OrderQueue;     // 입력 큐 
    queue<int> NumQueue;       // 기준 큐
    stack<int> TmpStack;        // 임시스택
    vector<string> answer;      // 정답스택
    // 수열 스택 입력 
    cin >> num;
    for(int i=1; i <= num; i++)
    {
        int tmp; 
        cin >> tmp;
        // 4 3 6 8 7 5 2 1
        OrderQueue.push(tmp);
        // 1 2 3 4 5 6 7 8 
        NumQueue.push(i);
    }
    for(int i=0; i < num; i++)
    {   
        while(!OrderQueue.empty())
        {   // 임시스택이 비어있을경우나 스택의 상단과 인풋값이 맞을때 까지 
            if(TmpStack.empty() || TmpStack.top() != OrderQueue.front())
            {   // TmpStack : 1 2 3 4
                TmpStack.push(NumQueue.front());
                // NumQueue : 5 6 7 8
                if(!NumQueue.empty())
                    NumQueue.pop();
                else
                    break;
                answer.push_back("+");  
            }   
            else if(TmpStack.top() == OrderQueue.front())
            {   // TmpStack : 1 2 3 [4].. pop
                TmpStack.pop();
                answer.push_back("-");
                OrderQueue.pop();
                break;
            }       
        } 
    }
    
    if(!TmpStack.empty())
    {
        answer.clear();
        answer.push_back("NO");
    }
    for(auto el : answer)
        cout << el << '\n'; 
}

결과

SOL

입력큐에 임의의 수열 입력 & 기준 큐 생성
1. 입력 큐 : [ 4 3 6 8 7 5 2 1 ]
2. 기준 큐 : [ 1 2 3 4 5 6 7 8 ]
임시스택의 top 입력큐의 front 값과 다르면
1. 같을 때 까지 기준큐 pop & 임시 스택에 기준 큐 값 push
  1. 정답 스택 입력 ... ‘ + ’
임시스택의 top 입력큐의 front 값과 같으면
1. 다를 때 까지 임시스택 pop & 입력 큐 pop
  1. 정답 스택 입력 ... ‘ - ‘
    
    즉. ‘ - ‘ 는 임의의 수열의 원소가 처리 되었다는 뜻 !

Work flow

n = 8

임의의 수열 : [ 4 3 6 8 7 5 2 1 ]

기준 수열 : [ 1 2 3 4 5 6 7 8 ]

임시 수열 : [ ]

임의의 수열의 원소 [ 4 ]
1. 기준 수열 : [ 5 6 7 8 ] ... 1 2 3 4 pop - queue
  1. 계산결과 ‘ + + + + ’
2. 임시 수열 : [ 1 2 3 4 ] ... 1 2 3 4 push - stack
  1. 임의의 수열의 원소 [ 4 ]와 임시수열 top 값과 같음.
    1. 임시수열 : [ 1 2 3 ] ... 4 pop - stack
      1. 계산결과 ‘ - ’