[백준/BOJ] 18258번 : 큐 2, 1021번 : 회전하는 큐, 5430번 : AC (큐, 덱)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 18258번 : '큐 2', 1021번 : '회전하는 큐', 5430번 : 'AC' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver ~ Gold 티어에 해당하며, 문제를 풀이하기 위해 큐, 덱에 대한 이해가 필요합니다.

 

 

18258번 : 큐 2

 

큐를 직접 구현해보는 문제입니다.

이전의 강의글이었다면 큐를 직접 구현해보았겠지만, 여기서는 큐 라이브러리를 사용할 줄 안다고 가정하고, 바로 활용해보도록 하겠습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    queue<int> Queue;

    while(N--) {
        string str; cin >> str;

        if(str == "push") {
            int val; cin >> val;
            Queue.push(val);
        }
        else if(str == "pop" && !Queue.empty()) {
            cout << Queue.front() << "\n";
            Queue.pop();
        }
        else if(str == "size") cout << Queue.size() << "\n";
        else if(str == "empty") cout << Queue.empty() << "\n";
        else if(str == "front" && !Queue.empty()) cout << Queue.front() << "\n";
        else if(str == "back" && !Queue.empty()) cout << Queue.back() << "\n";
        else cout << "-1\n";
    }
}

 

위와 같이 큐 라이브러리를 활용하여 그냥 Queue의 함수들을 사용해주면 쉽게 해결이 가능합니다.

C++의 string 헤더파일에서 문자열을 비교할 때는 그냥 == 연산으로 비교해줄 수 있습니다.

명령어에 따라 개행문자(\n)을 출력해야하는 경우도 있고 그렇지 않은 경우도 있으므로 \n은 각자 출력해주도록 합니다.

 

 

 

 

1021번 : 회전하는 큐

 

큐를 적절히 회전하여 처음에 있는 수들만 뽑아낸다고 했을 때, 입력으로 주어진 수 순서대로 뽑으려면 최소 몇 번의 이동을 해야하는지 묻는 문제입니다.

단방향 이동만 있었다면 큐로 구현이 가능하겠지만, 여기서는 양방향으로 배열을 이동시켜야 하므로 덱을 활용하여 문제를 풀어주어야 수월합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<int> key(M);
    for(int i=0; i<M; i++) cin >> key[i];

    deque<int> Deque;
    for(int i=1; i<=N; i++) Deque.push_back(i);

    int cnt = 0;
    for(int i=0; i<M; i++) {
        int location;
        for(int j=0; j<Deque.size(); j++)
            if(Deque[j] == key[i]) {
                location = j;
                break;
            }

        if(location <= Deque.size()/2) {
            while(Deque.front() != key[i]) {
                Deque.push_back(Deque.front());
                Deque.pop_front();
                cnt++;
            }
            Deque.pop_front();
        }
        else {
            while(Deque.back() != key[i]) {
                Deque.push_front(Deque.back());
                Deque.pop_back();
                cnt++;
            }
            Deque.pop_back();
            cnt++;
        }
    }
    cout << cnt;
}

 

위와 같이 덱에서 찾는 key가 몇 번째 위치에 존재하는지 파악한 후, size/2보다 왼쪽에 있으면 정방향으로 회전을, 그렇지 않다면 역방향으로 회전시켜 뽑아주는 것이 더 빠릅니다. (이를 비교하는 것은 덱에 원소가 홀수개 있을 때와 짝수개 있을 때를 나누어 생각해보면 됩니다.)

따라서 방향성을 먼저 정하고 덱을 회전시켜서 카운트 해주면 됩니다.

 

 

 

 

5430번 : AC

 

R 또는 D에 해당하는 명령어를 적절히 수행하여 결과값을 출력하는 문제입니다.

방향을 뒤집어 꺼내야하는 경우가 존재하므로 덱을 활용하여 문제를 푸는 편이 쉽습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;
    while(T--) {
        string Function; cin >> Function;
        int numCnt; cin >> numCnt;
        string num; cin >> num;

        string tempNum;
        deque<int> Deque;
        for(int i=0; i<num.length(); i++) {
            if(num[i] >= '0' && num[i] <= '9')
                tempNum += num[i];
            else if((num[i] == ',' || num[i] == ']') && !tempNum.empty()) {
                Deque.push_back(stoi(tempNum));
                tempNum.clear();
            }
        }

        bool isReversed = false, isError = false;
        for(int i=0; i<Function.length(); i++) {
            if(Function[i] == 'R') isReversed = !isReversed;
            else {
                if(!Deque.empty()) {
                    if(!isReversed) Deque.pop_front();
                    else Deque.pop_back();
                }
                else {
                    isError = true;
                    cout << "error\n";
                    break;
                }
            }
        }

        if(!isError) {
            cout << "[";

            while(!Deque.empty()) {
                if(!isReversed) {
                    cout << Deque.front();
                    Deque.pop_front();
                }
                else {
                    cout << Deque.back();
                    Deque.pop_back();
                }

                if(!Deque.empty()) cout << ",";
            }

            cout << "]\n";
        }
    }
}

 

대체로 어렵지 않으나 입력된 문자열에서 [나 , 등을 모두 빼고 읽어주어야 하기 때문에 그 부분이 처리하기 조금 까다로울 수 있는 문제입니다.

또한 error가 발생하는 경우도 찾아주어야 하므로 bool 변수를 하나 활용하여 error가 발생하였는지를 체크해주면 좋습니다.

저 같은 경우에는 isReversed 변수를 활용하여 false인 경우 덱의 front에서, true인 경우 뒤집힌 것이므로 덱의 back에서 pop을 해주도록 하였습니다.

 

 

 

---

이상으로 BOJ의 단계별로 풀어보기에서 큐, 덱에 대한 문제들은 모두 해결하였고, 다음 포스트에서는 '분할 정복' 문제들을 해결해보도록 하겠습니다.