[BOJ] 큐, 덱 2

📝10866번: 덱

문제 설명

덱

해결 방법

C++ STL deque를 이용해서 구현한다.

💻소스코드

#include <iostream>
#include <deque>

using namespace std;

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

    int N;
    cin >> N;
    deque<int> dq;
    string str;
    int num;

    for (int i = 0; i < N; i++) {
        cin >> str;

        if (str == "push_front") {
            cin >> num;
            dq.push_front(num);
        }
        else if (str == "push_back") {
            cin >> num;
            dq.push_back(num);
        }
        else if (str == "pop_front") {
            if (!dq.empty()) {
                cout << dq.front() << "\n";
                dq.pop_front();
            }
            else
                cout << "-1\n";
        }
        else if (str == "pop_back") {
            if (!dq.empty()) {
                cout << dq.back() << "\n";
                dq.pop_back();
            }
            else
                cout << "-1\n";
        }
        else if (str == "size") {
            cout << dq.size() << "\n";
        }
        else if (str == "empty") {
            if (!dq.empty())
                cout << "0\n";
            else
                cout << "1\n";
        }
        else if (str == "front") {
            if (!dq.empty())
                cout << dq.front() << "\n";
            else
                cout << "-1\n";
        }
        else if (str == "back") {
            if (!dq.empty())
                cout << dq.back() << "\n";
            else
                cout << "-1\n";
        }
    }
    return 0;
}

---

📝1021번: 회전하는 큐

문제 설명

회전하는 큐

해결 방법

1. 뽑으려는 수의 위치가 deque에서 왼쪽, 오른쪽 중 어느 방향과 더 가까운지를 판단한다.
2. 왼쪽, 오른쪽 중 이동 횟수가 적은 방향으로 push, pop을 실행한다.
3. 총 이동 횟수를 출력한다.

큐의 맨 앞과 맨 뒤에서 원소의 삽입, 삭제가 자유로워야 하므로 deque를 활용한다.
N을 입력으로 받아서 deque에 1부터 N까지 push_back 한다.
뽑으려는 수의 위치를 pos_idx로 선언하고 deque를 인덱스로 접근하여 pos를 찾는다. (deque의 []연산자 사용)
dq.size() - pos_idx > pos_idx 의 경우, pos가 맨 앞이랑 더 가깝다는 의미이므로 왼쪽으로 이동한다.
그 외의 경우 오른쪽에 가깝거나 왼쪽, 오른쪽 이동 횟수가 같은 경우이므로 오른쪽으로 이동한다.
이동횟수를 카운트하고 deque에서 원소를 삭제한다.

💻소스코드

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    // 회전하는 큐
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, pos;  // 큐의 크기, 뽑아내려고 하는 수의 개수, 뽑아내려고 하는 수의 위치
    deque<int> dq;  // 회전하는 큐
    int cnt = 0;	// 최소횟수 카운트

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        dq.push_back(i);
    }

    for (int i = 0; i < M; i++) {
        // deque에서 pos의 위치가 맨 앞이랑 가까운지 맨 뒤랑 가까운지 판단
        cin >> pos;
        int pos_idx = 0;
        for (int j = 0; j < dq.size(); j++) {
            if (dq[j] == pos) {
                pos_idx = j;
                break;
            }
        }
        if (pos_idx < dq.size() - pos_idx) {
            // 왼쪽에 가까우므로 왼쪽으로 이동
            while (pos != dq.front()) {
                dq.push_back(dq.front());
                dq.pop_front();
                cnt++;
            }
            dq.pop_front();
        }
        else {
            // 오른쪽에 가깝거나 중간이므로 오른쪽으로 이동
            while (pos != dq.front()) {
                dq.push_front(dq.back());
                dq.pop_back();
                cnt++;
            }
            dq.pop_front();
        }
    }

    cout << cnt << "\n";
	return 0;
}

---

📝5430번: AC

문제 설명

AC

해결 방법

문제에서 요구하는 대로 작성했다. 입력받은 명령어 순서 및 조합에 따라서 맨 앞 또는 맨 뒤의 원소를 삭제해야 하기 때문에 deque를 사용했다. 입력 받은 배열에서 "[,]"를 제외한 원소들을 먼저 deque에 push_back하고 error flag를 이용하여 에러를 판단하고 rev flag를 이용하여 뒤집어진 배열인지를 판단했다.

💻소스코드

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

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

    int T, n;   //  테스트 케이스 개수, 배열에 들어있는 수의 개수
    string p, input;   // 수행할 함수, 입력 배열

    cin >> T;
    for (int i = 0; i < T; i++) {
        bool err = false;
        string ele = "";    // 두 자리 수 이상 원소 처리
        deque<int> dq;
        cin >> p;
        cin >> n;
        cin >> input;
        if (n != 0) {
            for (int j = 0; j < input.size(); j++) {    // 입력받은 배열에서 [ , ] 를 제외하고 deque에 push
                if (input[j] == '[' || input[j] == ']' || input[j] == ',') {
                    if (input[j] != '[') {
                        dq.push_back(stoi(ele));
                        ele = "";
                    }
                }
                else
                    ele += input[j];
            }
        }
        int rev = 1;    // 배열이 뒤집어졌는지 판단, 1이면 정상, -1이면 뒤집힘
        for (int j = 0; j < p.size(); j++) {
            if (p[j] == 'R') {  // 'R' 명령어를 만나면 배열을 뒤집는다.
                rev *= -1;
            }
            else if (p[j] == 'D') {     // 'D' 명령어를 만났을 때
                if (dq.size() == 0) {   // 배열이 비어있으면 에러 출력
                    cout << "error\n";
                    err = true;
                    break;
                }
                else {
                    if (rev == 1)   // 배열의 순서가
                        dq.pop_front(); // 정방향이면 앞에서 pop
                    else
                        dq.pop_back();  // 역방향이면 뒤에서 pop
                }
            }
        }
        if (!err) {
            cout << '[';
            if (rev == 1) { // 정방향이면 정방향대로 출력
                while (!dq.empty()) {
                    cout << dq.front();
                    dq.pop_front();
                    if (dq.size() != 0)
                        cout << ',';
                }
            }
            else {  // 역방향이면 역방향대로 출력
                while (!dq.empty()) {
                    cout << dq.back();
                    dq.pop_back();
                    if (dq.size() != 0)
                        cout << ',';
                }
            }
            cout << "]\n";
        }
    }
}

---