백준 1874번 스택 수열

문제 링크입니다: https://www.acmicpc.net/problem/1874

스택과 큐를 적절히 이용하여 풀어야했던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 큐를 선언하여 원하는 순서를 선언한 큐에 넣습니다.

2. 큐의 front에 있는 숫자에 대해 먼저 처리해줍니다.

i) num이 해당 숫자가 될 때까지 +

ii) 해당 숫자에 대해서 처리했으므로 큐와 스택 pop을 진행하고 -

3. 이후에는 반복문 내에서 나머지 숫자들을 아래와 같은 세가지 경우에 대해 처리해줍니다.

i) 스택이 비었거나 현재 원하는 숫자 > 스택의 top 일 경우

ii) 현재 원하는 숫자 == 스택의 top

iii) 현재 원하는 숫자 < 스택의 top

4. 3번을 진행한 후 불가능한 경우이면 "NO"를 출력하고 가능한 경우이면 결과 문자열을 출력해줍니다.

#include <iostream>

#include <string>

#include <stack>

#include <vector>

#include <queue>

using namespace std;

 

stack<int> s;

queue<int> q;

string result;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        //원하는 순서

        for (int i = 0; i < N; i++)

        {

                 int temp;

                 cin >> temp;

 

                 q.push(temp);

        }

 

        int num = 1;

        //처음 원하는 숫자 처리

        for (int i = 0; i < q.front(); i++)

        {

                 s.push(num++);

                 result += '+';

        }

        //처음 원하는 숫자를 처리했으므로 pop

        result += '-';

        q.pop();

        s.pop();

 

        bool impossible = false;

        while (1)

        {

                 if (q.empty())

                         break;

                 int cur = q.front();

 

                 //스택이 비었거나 현재 스택의 top보다 원하는 숫자가 클 경우 push

                 if (s.empty() || cur > s.top())

                 {

                         s.push(num++);

                         result += '+';

                 }

                 //현재 원하는 숫자가 스택의 top일 경우 pop

                 else if (cur == s.top())

                 {

                         result += '-';

                         q.pop();

                         s.pop();

                 }

                 //불가능한 경우: 현재 원하는 숫자가 스택의 top보다 작다

                 else if (cur < s.top())

                 {

                         impossible = true;

                         break;

                 }

        }

 

        if (impossible)

                 cout << "NO\n";

        else

                 for (int i = 0; i < result.size(); i++)

                         cout << result[i] << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~