1021번 : 회전하는 큐

Backjoon Online Judge 

"1021번 : 회전하는 큐" 문제입니다.

문제 링크 : https://www.acmicpc.net/problem/1021

문제에서 3가지 연산을 쉽게 구현하기 위해 Queue 라이브러리를 사용하여 Deque를 만들었습니다.

 - 처음 위치는 위의 3가지 연산 과정에서 계속 바뀌므로 편의를 위해 처음 위치에 해당하는 '1'~'큐의 크기'까지를 각각 큐의 값으로 입력하였습니다.

 - 원소를 하나씩 뽑아낼 때 마다 다음번 뽑아내려는 위치를 얻고 이는 처음 큐에서의 위치이므로 현재 그 위치가 어디로 이동하였는지 확인하기 위해 큐의 처음 위치부터 접근하여 뽑아내야 할 위치를 찾았습니다. 

 - 뽑아내려는 할 위치를 찾은 경우 '뽑아낼 위치' 과 '큐의 크기 - 뽑아낼 위치' 를 비교하여 큐의 이동 방향을 정했습니다. (2, 3번 연산 횟수를 최소화 하기 위해)

- 위 문장을 보충설명 하자면 뽑아낼 위치로 접근하기 위한 방법은 큐를 왼쪽으로 계속 이동하여(2번 연산) 접근하거나, 큐를 오른쪽으로 계속 이동하여(3번 연산) 접근하는 방법이 있는데 뽑아낼 위치가 오른쪽이 있다면 (큐의 크기와 크게 차이나지 않는 곳) 3번 연산을 통해 해당 위치에 접근하는 것이 더 연산 횟수가 적어집니다.

- 위 과정을 M번 만큼 반복하여 2번, 3번 연산의 최솟값을 출력하게 됩니다.

코드는 C++로 작성하였습니다.

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int main() {
    deque<int> dq;
    int N, M, tmp, i; 
    int answer = 0;
 
    cin >> N >> M;
 
    while (N--)
        dq.push_front(N+1);
 
    while (M--) {
        cin >> tmp;
        for (i = 0; i < dq.size(); i++) {
            if (dq[i] == tmp)
                break;
        }
 
        if (i < dq.size() - i) {
            while (i--) {
                dq.push_back(dq.front());
                dq.pop_front();
                answer++;
            }
        }
        else {
            i = dq.size() - i;
            while (i--) {
                dq.push_front(dq.back());
                dq.pop_back();
                answer++;
            }
        }
 
        dq.pop_front();
    }
 
    cout << answer << "\n";
    return 0;
}