[백준 1874번] 스택 수열 (C++)

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

이번 포스팅에서는 백준 1874번 문제를 학습합니다.

 

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

솔직하게 말하자면 아직도 이 문제를 100프로 이해했다고 말하기 어렵다.

예제 입력 1을 바탕으로 문제를 설명하자면,

4를 뽑기 위해 스택에서 [push, push, push, push,] 연산을 한 후, [pop]를 통해 뽑는다.

그 후 3을 뽑기 위해 [pop]를 한다. (이미 스택의 최상위 부분에 3이 있기 때문에 따로 push를 할 필요가 없다)

그 후 6을 뽑기 위해 [push, push]를 한 다음 [pop]를 통해 뽑는다.

따라서 우리는 1부터 8까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

접근 아이디어

1. 스택에 들어올 수 있는 가장 작은 수는 1이므로 1보다 큰 수가 들어왔다면 처음으로 뽑을 수의 크기 만큼 string 에 '+'를 추가해준다.

2. 원하는 수를 뽑으려면 '-'가 무조건 필요하다.

3. 바로 뽑아야 할 수 보다 큰 수가 스택에 쌓여있다면 스택 수열을 만들 수 없다. ("NO" 출력)

4. 뽑아야 할 수가 가장 최상위 스택에 존재한다면 push 없이 바로 pop을 진행한다. (= string 에 '-'를 추가해준다.)

5. 1 이상 처음 입력 받은 수 이하의 수열을 만드는 동안 추가된 부호들이 담긴 string을 출력해준다.

 

 

 

 

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
    stack<int> st;
    string str;
    int i = 1;
    int T;
    cin >> T;

    while (T--)
    {
        int num;
        cin >> num;

        if (i <= num)
        {
            while (i <= num)
            {
                st.push(i);
                str += '+';
                i++;
            }
            st.pop();
            str += '-';
        }
        else     // i > num
        {
            if (st.top() < num)
            {
                cout << "NO" <<"\n";
                return 0; // NO가 출력되면 바로 종료하기 위해서
               
            }
            else
            {
                st.pop();
                str += '-';
            }
        }
    }
    for (int j = 0; j < str.length(); j++)
        {
            cout << str[j] << "\n";
        }

    return 0;
}

 

 

 

*유의사항

- 공부 중인 인공지능공학과 대학생이 정리해서 남긴 정리입니다.

- 정확하지 않거나, 틀린 점이 있다면 댓글로 알려주시면 감사하겠습니다.