[BOJ/Silver 2] 백준 27497 알파벳 블록(C++)

문제 링크

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

27497번: 알파벳 블록

 

문제

스타는 알파벳 블록을 일렬로 조립하여 문자열을 만드는 게임을 만들었다. 각 블록에는 문자 하나가 적혀 있으며 게임에는 각각 다음 기능을 수행하는 세 개의 버튼이 있다.

• 문자열 맨 뒤에 블록 추가
• 문자열 맨 앞에 블록 추가
• 문자열을 구성하는 블록 중 가장 나중에 추가된 블록 제거

 

게임은 처음에 빈 문자열로 시작하며 빈 문자열일 때 문자열을 구성하는 블록 중 가장 나중에 추가된 블록을 제거하는 버튼을 누를 경우 아무런 동작도 하지 않는다. 버튼을 누른 횟수와 누른 버튼이 순서대로 주어질 때 완성된 문자열을 구하여라.

 

입력

첫째 줄에 버튼을 누른 횟수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개의 줄에는 버튼을 누른 순서대로 누른 버튼에 대한 정보를 주며 아래와 같은 형식으로 주어진다.

• 1 c : 문자열 맨 뒤에 c가 적힌 블록 추가
• 2 c : 문자열 맨 앞에 c가 적힌 블록 추가
• 3 : 문자열을 구성하는 블록 중 가장 나중에 추가된 블록 제거

 

c는 알파벳 대문자 또는 소문자로 주어진다.

 

출력

완성된 문자열을 출력한다. 완성된 문자열이 빈 문자열인 경우 0을 출력한다.

 

예제 입력 1

5
1 a
2 b
1 c
3
3

예제 출력 1

a

• 버튼을 한 번 눌렀을 때, 문자열은 “a”가 된다.
• 버튼을 두 번 눌렀을 때, 문자열은 “ba”가 된다.
• 버튼을 세 번 눌렀을 때, 문자열은 “bac”가 된다.
• 버튼을 네 번 눌렀을 때, 가장 나중에 추가된 블록이 제거되어 문자열은 “ba”가 된다.
• 버튼을 다섯 번 눌렀을 때, 가장 나중에 추가된 블록이 제거되어 문자열은 “a”가 된다.

예제 입력 2

9
1 c
2 n
1 h
1 o
2 i
1 R
3
2 S
1 n

예제 출력 2

Sinchon

예제 입력 3

7
2 Y
3
1 R
3
3
2 n
2 O

예제 출력 3

On

예제 입력 4

11
1 u
3
2 z
3
1 s
2 A
3
1 a
3
3
3

예제 출력 4

0

 

알고리즘 분류

• 자료 구조
• 문자열

 

풀이

먼저 문자열을 만들 때 덱을 사용한다. 또한 스택을 사용하여 마지막 문자를 앞에 추가했는지, 뒤에 추가했는지를 기록한다.

1번 버튼을 누르면 문자를 덱의 back에 push하고 스택에 false를 push한다.

2번 버튼을 누르면 문자를 덱의 front에 push하고 스택에 true를 push한다.

3번 버튼을 누르면 스택의 top을 확인하여, true면 덱의 front를, false면 덱의 back을 pop하고 스택의 top을 pop한다.

버튼을 N번 누른 후 결과를 확인한다.

덱이 비어있다면 0을 출력한다.

덱이 비어있지 않다면 덱의 front부터 하나씩 출력하면서 pop한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
char C;
stack<bool> S;
deque<char> Answer;

void input() {
    cin >> N;
    while (N--) {
        cin >> M;
        if (M == 1) {
            cin >> C;
            Answer.push_back(C);
            S.push(false);
        }
        else if (M == 2) {
            cin >> C;
            Answer.push_front(C);
            S.push(true);
        }
        else if (M == 3) {
            if (S.empty()) {
                continue;
            }

            if (S.top()) {
                Answer.pop_front();
            }
            else {
                Answer.pop_back();
            }

            S.pop();
        }
    };
}

void find_Answer() {
    if (Answer.empty()) {
        cout << "0\n";
    }
    else {
        while (!Answer.empty()) {
            cout << Answer.front();
            Answer.pop_front();
        };
        cout << "\n";
    }
}

int main() {
    FASTIO
    input();
    find_Answer();

    return 0;
}