[BOJ] 회전하는 큐(1021)

[백준(BOJ)] 회전하는 큐(1021) C++

문제 : BOJ_1021번 회전하는 큐

문제 설명

Deque

1 ~ N까지의 수가 양방향 순환 큐에 나열되어 있는 상태에서 M 개의 원소를 뽑아야 합니다.

이때 나열되어 있는 방식이 순환 큐이기 때문에 첫 번째 위치의 원소만 뽑아낼 수 있고, 첫 번째 위치가 아니라면 순환으로 왼쪽 혹은 오른쪽으로 회전하며 원소를 첫 번째 위치로 이동시켜 뽑아야 합니다.

이때 왼쪽 오른쪽으로 회전하는 횟수의 최소를 구해야 합니다.

---

Solution

N이 50보다 작기 때문에 무슨 방법을 쓰든 구현만 해낸다면 정답 처리가 될 것입니다.

저는 deque을 사용했는데, 이유는 다음과 같습니다.

• 첫 번째 원소를 삽입, 삭제할 수 있다.
• 마지막 원소를 삽입, 삭제할 수도 있다.
• 인덱스를 순회하면서 해당 인덱스 안에 어떤 수가 들어있는지 확인할 수 있다.
  왼쪽이나 오른쪽으로 순회하기 전, 인덱스를 순회하여 해당하는 수가 몇 번째 인덱스에 있는지 확인하고, 그 인덱스와 deque.size()를 비교하며 왼쪽으로 옮길지, 오른쪽으로 옮길지 정하면서 진행하면 해결할 수 있습니다.

---

Description

• 실제로 예제를 만들어 놓고, 예제에서 deque의 전체 사이즈와 인덱스를 비교해보고 식을 짜면 편합니다.

---

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main(void) {
    int N, M;
    cin >> N >> M;
    deque<int> d;
    for (int i = 1; i <= N; i++) d.push_back(i);
    int result = 0;
    for (int i = 0; i < M; i++) {
        int now;
        cin >> now;
        int idx = 0;
        for (int i = 0; i < d.size(); i++) {
            if (now == d[i]) {
                idx = i + 1;
                break;
            }
        }
        if (idx-1 < d.size() - idx+1) {
            result += idx - 1;
            for (int i = 1; i < idx; i++) {
                int val = d.front();
                d.push_back(val);
                d.pop_front();
            }
            d.pop_front();
        }
        else {
            result += d.size() - idx+1;
            for (int i = 1; i <= d.size() - idx; i++) {
                int val = d.back();
                d.push_front(val);
                d.pop_back();
            }
            d.pop_back();
        }
    }
    cout << result << '\n';
    return 0;
}