[Baekjoon, C++] 1021번 : 회전하는 큐

백준 단계별 풀기에서 큐,덱 여섯번째 문제이다.
링크는 아래와 같다.

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

---

 

백준 1021번 문제, 입력, 출력

---

백준 1021번 입출력 예제 1, 2, 3, 4 

---

1. deque를 활용한 문제이다. deque를 활용하면, 회전하는 큐를 구현할 수 있다.

 

2. 2번, 3번 연산을 하는 최소값을 구하려면, 우선 덱(deque)에서 빼내고자 하는 정수의 위치를 알 수 있어야한다. 그래야 2번 연산을 할지, 3번 연산을 할지 선택할 수 있기 때문이다. 처음에는 단순히, 덱의 사이즈를 반으로 나눠 구하고자 하는 값이 왼쪽이면 3번연산, 오른쪽이면 2번연산을 한다고 생각했다. 그러면 해당 정수의 위치를 찾기 위한 연산을 할 필요가 없기 때문이였다. 

---

잘못된 접근의 코드

#include<iostream>
#include<deque>
#include<queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int sizeOfDeque;
    int numOfSearch;
    int countOfOperation = 0;
    int secondOp = 0;
    int thirdOp = 0;
    deque<int> deque;
    queue<int> que;

    cin >> sizeOfDeque;
    for (int i = 1; i <= sizeOfDeque; i++) {
        deque.push_back(i);
    }

    cin >> numOfSearch;
    for (int i = 0; i < numOfSearch; i++) {
        int num;
        cin >> num;
        que.push(num);
    }

    while (!que.empty()) {
        int nowFind = que.front();
        int nowDequeValue;

        if ((deque.size() / 2) < nowFind - secondOp + thirdOp) {
            nowDequeValue = deque.back();
            
            deque.push_front(nowDequeValue);
            deque.pop_back();
            thirdOp++;
            countOfOperation++;
          
        }
        else {
            nowDequeValue = deque.front();
            if (nowDequeValue == nowFind) {
                que.pop();
                deque.pop_front();
                secondOp = 0;
                thirdOp = 0;
                continue;
            }
            else {
                deque.push_back(nowDequeValue);
                deque.pop_front();
                secondOp++;
                countOfOperation++;
            }
        }
    }

    cout << countOfOperation;
	
	return 0;
}

---

(2.)의 단순히 어느쪽으로 회전해야하는지에 대한 조건으로 큐의 사이즈를 반으로 나누어서 판단하면 될 것이라고 접근한 것이 미스였다. 문제점이, 덱에서 자리값, 즉 index로 비교해야한다, 덱이 하나씩 뺄 때마다 변하기 때문이다. 빼고자 하는 정수값의 위치를 알아내야하는 연산이 필요했었다. 

---

수정된 코드

#include<iostream>
#include<deque>
#include<queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int sizeOfDeque;
    int numOfSearch;
    int countOfOperation = 0;
    deque<int> deque;
    queue<int> que;

    cin >> sizeOfDeque;
    for (int i = 1; i <= sizeOfDeque; i++) {
        deque.push_back(i);
    }

    cin >> numOfSearch;
    for (int i = 0; i < numOfSearch; i++) {
        int num;
        cin >> num;
        que.push(num);
    }

    for (int k = 0; k < numOfSearch; k++) {
        int nowIndex = 0;
        int nowFind = que.front();
        int nowDequeValue;
        for (int i = 0; i < deque.size(); i++) {
            if (nowFind == deque[i]) {
                nowIndex = i;
                break;
            }
        }

        if (nowIndex >= deque.size() - nowIndex) {
            while (true) {
                nowDequeValue = deque.back();
                if (deque.front() == nowFind) {
                    que.pop();
                    deque.pop_front();
                    break;
                }
                countOfOperation++;
                deque.push_front(nowDequeValue);
                deque.pop_back();
            }
          
        }
        else {           
            while (true) {
                nowDequeValue = deque.front();
                if (deque.front() == nowFind) {
                    que.pop();
                    deque.pop_front();
                    break;
                }
                countOfOperation++;
                deque.push_back(nowDequeValue);
                deque.pop_front();
            }
        }
    }

    cout << countOfOperation;
	
	return 0;
}

---

이상으로 1021번을 마치겠다.