[C++] BOJ 5430번: AC

학교에서 진행하는 수업에서 알고리즘 문제를 공유하기 위해 문제를 풀어보았다.

 

문제의 난이도는 골드 5로, 정답률은 약 20%이다. 시간 제한은 1초이다.

문제 링크

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

문제 설명

 이번 문제는 정수 배열에 연산을 한 결과를 출력하는 문제이다. 연산의 종류는 뒤집기 R과 버리기 D가 있다. 뒤집기 R은 배열의 순서를 뒤집기(Reverse)하는 함수이고, D는 첫 번째 수를 버리는 (pop_first) 함수이다. 배열이 비어 있을 때 D를 사용하면 에러가 발생한다.

문제 분석

 문제에서 주어지는 입력을 보면 배열이 문자열 [1, 2, 3, 4]와 같은 형태로 입력이 들어온다. 문제를 풀기 위해서는 이러한 문자열을 배열로 파싱하는 과정이 필요하다. 필자는 입력된 문자열을 배열 대신 Deque으로 전환하였다.

 

 마찬가지로 결과를 출력할 때에도 [1, 3]과 같은 문자열로 결과를 출력해야 한다. Deque에 있는 값들을 문자열로 파싱하여 출력하는 과정이 한 번 더 필요하다.

 

 뒤집기 R과 버리기 D를 수행할 때 실제 배열을 뒤집는 방식으로 구현하면 '시간 초과'가 발생한다. 문제를 풀 때에 C++에서는 std::reverse(), Python에서는 arr[::-1]을 사용하지 않아야 한다. 따라서 문제 해결을 위해 배열을 사용하는 대신 pop과 push를 front와 back 양쪽에서 할 수 있는 Deque 자료구조를 활용해 문제를 푸는 것이 적합하다.

 

 따라서 이번 문제의 핵심 유형은 아래와 같다고 할 수 있다.

 - 문자열 파싱

 - Deque (덱)

자료 구조 및 알고리즘

Deque (덱)

https://ko.wikipedia.org/wiki/덱_(자료_구조)

 Queue 자료구조는 FIFO형으로 처음 들어온 요소는 먼저 나가는 것만 가능하다면, Deque은 앞으로도 데이터를 넣고 뺄 수 있고 뒤로도 데이터를 넣고 뺄 수 있는 자료구조이다. Deque이 가진 특성 상 프로그래머가 사용하기에 따라 Stack으로도, Queue로도 활용할 수 있다. Deque에서 이루어지는 연산은 아래와 같다.

1. 앞으로 넣기
2. 뒤로 넣기
3. 앞에서 빼기
4. 뒤에서 빼기

문제 풀이

 문제를 풀기 위해서는 다음 과정이 필요하다.

1. 입력으로 들어온 문자열을 정수형 데이터로 파싱하는 과정
2. 파싱한 데이터를 기반으로 R 또는 D 연산을 수행하는 과정
3. 모든 연산이 끝난 후의 결과를 문자열 배열로 보여주는 과정

 해당 문제에서 [1, 2, 3, 4]와 같은 입력으로 들어 온 문자열을 deque으로 전환하기 위해 parseArrToDeque이라는 함수를 구현하였다.

구현한 코드는 다음과 같다.

void parseArrToDeque(string arrStr, deque<int> &dq)
{
    int inputSize = arrStr.size();

    bool isNumber = false;
    int number = 0;

    for (int i = 0; i < inputSize; i++)
    {
        if (arrStr[i] == '[' || arrStr[i] == ',' || arrStr[i] == ']')
        {
            if (isNumber)
            {
                dq.push_back(number);
            }
            isNumber = false;
        }
        else if (isNumber == false)
        {
            number = arrStr[i] - '0';
            isNumber = true;
        }
        else
        {
            number = number * 10 + (arrStr[i] - '0');
        }
    }
}

 

 

 해당 문제에서 Deque은 함수 R 연산이 짝수 번 이루어지면 isR이라는 flag의 값이 false가, 홀수 번 이루어지면 isR flag의 값이 true가 되도록 하였다. isR이 false일 때 함수 D 연산을 수행하면 앞에서 빼기를 수행하고, isR이 true일 때 D 연산을 하면 뒤에서 빼기를 수행하는 방식으로 활용하였다.

 

 전체 코드는 아래와 같다.

전체 코드

// https://www.acmicpc.net/problem/5430
// BOJ 5430번 - AC

#include <iostream>
#include <deque>

using namespace std;

void parseArrToDeque(string arrStr, deque<int>& dq) {
    int inputSize = arrStr.size();

    bool isNumber = false;
    int number = 0;

    for (int i = 0; i < inputSize; i++)
    {
        if(arrStr[i] == '[' || arrStr[i] == ',' || arrStr[i] == ']') {
            if(isNumber) {
                dq.push_back(number);
            }
            isNumber = false;
        } else if(isNumber == false) {
            number = arrStr[i] - '0';
            isNumber = true;
        } else {
            number = number * 10 + (arrStr[i] - '0');
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;

    cin >> T;

    for (int i = 0; i < T; i++)
    {
        string p;
        string arrStr;
        bool isR = false;
        cin >> p;
        int n;
        cin >> n;
        deque<int> dq;
        cin >> arrStr;
        parseArrToDeque(arrStr, dq);

        bool errorFlag = false;

        for(char ch: p) {
            if (ch == 'R') {
                isR = !isR;
            } else {
                if (dq.empty()) {
                    errorFlag = true;
                    break;
                } else if(isR) {
                    dq.pop_back();
                } else {
                    dq.pop_front();
                }
            }
        }

        if (errorFlag) {
            cout << "error" << '\n';
            continue;
        }

        cout << "[";
        while(!dq.empty()) {
            if (isR) {
                cout << dq.back();
                if (dq.size() != 1)
                    cout << ',';
                dq.pop_back();
            } else {
                cout << dq.front();
                if (dq.size() != 1)
                    cout << ',';
                dq.pop_front();
            }
        }
        cout << "]\n";
    }

    return 0;
}