Home BOJ - 1874 - 스택 수열
Post
Cancel

BOJ - 1874 - 스택 수열

BOJ - 1874 - 스택 수열

문제


1874번: 스택 수열

https://user-images.githubusercontent.com/71277820/162958607-c970b95a-3474-42e5-b49f-c7bd3617ea86.png

문제 개념


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

구현 - vector 사용


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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 사용


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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'; 
}

결과


https://user-images.githubusercontent.com/71277820/162963879-5e0b4b71-ef79-49a1-83ac-00d0aa3836a8.png

SOL


  1. 입력큐에 임의의 수열 입력 & 기준 큐 생성
    1. 입력 큐 : [ 4 3 6 8 7 5 2 1 ]
    2. 기준 큐 : [ 1 2 3 4 5 6 7 8 ]
  2. 임시스택의 top 입력큐의 front 값과 다르면
    1. 같을 때 까지 기준큐 pop & 임시 스택에 기준 큐 값 push
      1. 정답 스택 입력 … ‘ + ’
  3. 임시스택의 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 ]

임시 수열 : [ ]

  1. 임의의 수열의 원소 [ 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. 계산결과 ‘ - ’

알게된 점


vector로 stack이나 queue를 구현하는 것 보다 라이브러리를 이용하는게 훨씬 계산 속도가 빠르다.

Reference & 다른 PS 모음집


https://github.com/ggh-png/PS

STACK & QUEUE

This post is licensed under CC BY 4.0 by the author.