백준-1021번:회전하는 큐_C++

https://www.acmicpc.net/problem/1021

---

문제 조건

조건 1.

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다.

• 양 방향에서 원소의 삽입, 삭제가 가능한 deque를 사용해야겠다.
  • deque의 레퍼런스

---

조건 2-1.

첫 번째 원소를 뽑아낸다.
이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.

• deque.pop_front를 사용하자.

---

조건 2-2.

왼쪽으로 한 칸 이동시킨다.
이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.

• 가장 왼쪽의 원소(deque.front)를 복사해 놓고, 삭제(deque.pop_front)
• 복사한 값을 가장 오른쪽에 삽입(deque.push_back)

---

조건 2-3.

오른쪽으로 한 칸 이동시킨다.
이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

• 가장 오른쪽의 원소(deque.back)를 복사해 놓고, 삭제(deque.pop_back)
• 복사한 값을 가장 오른쪽에 삽입(deque.push_front)

---

구현할 내용

내용 1.

큐에 처음에 포함되어 있던 수 N이 주어진다.

• deque의 size는 입력받은 N과 같다.

그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.)

• 뽑아내려고 하는 원소의 위치는 M
• 위치의 기준은 처음 deque에서의 위치이므로, deque를 초기화할 때 1~N값을 가질 수 있게 하자.

이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

• 현재 deque.front가 f, 뽑아내려는 원소가 m이라고 할 때,

  1. f == m일 때 까지 deque를 오른쪽으로 이동
  2. 이동한 횟수가 cnt라고 할 때, cnt < deque.size - cnt가 true면 cnt번 움직인 것이고,
  3. cnt < deque.size-cnt가 false면 deque.size - cnt번 움직인 것으로 생각한다.

---

결과

#include<deque>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

int main() {

    int M = 0; int N = 0;
    deque<int> dq;   // deque
    int answer = 0;

    // M, N 입력부
    cin >> N >> M;

    // deque 초기화
    for (int i = 1; i <= N; i++) {
        dq.push_back(i);
    }
    
    // M개의 목표 원소 입력 받고, 최솟값 구하는 과정
    while (M-- > 0) {
        int goal; // goal element
        int cnt = 0;
        cin >> goal;

        // 목표 원소 찾고, 몇 번 움직였는지 기록
        while (dq.front() != goal) {
            int tmp = dq.front();
            dq.pop_front();
            dq.push_back(tmp);
            cnt++;
        }

        // 좌, 우 둘 중 덜 움직이는 방향 기록
        if (cnt < dq.size() - cnt)  answer += cnt;
        else                        answer += dq.size() - cnt;

        // 값 뽑아내기
        dq.pop_front();
    }
    
    cout << answer;


    return 0;
}

후기

• 문제 그대로 구현했는데, 주어진 입력의 크기가 작다 보니 알고리즘 자체를 최소값만큼 움직이게 하면 리소스가 훨씬 많이 들어갈 것 같아 그냥 구현 했다.