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

1021번: 회전하는 큐

 

문제

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

1021번: 회전하는 큐

 

 

풀이

자료구조인 덱을 사용해 원형 큐에서 M개의 수를 꺼내는 데 걸리는 최소 횟수를 구하는 문제다.

좌, 우로 움직일 수 있고 가장 앞 원소(front)를 꺼낼 때는 횟수가 증가하지 않는다는 특징이 있다.

1. 1부터 N을 덱에 넣는다.
2. 찾아야 하는 수를 확인한다.
3. 왼쪽부터 꺼내는 경우와 오른쪽부터 꺼내는 경우 중 빠른 경로를 찾는다.
4. 빠른 방향으로 원소를 찾을 때까지 이동하며 카운트를 증가시킨다.
5. 찾은 수를 pop 한다.
6. 2~5 과정을 M번 반복한다.
7. 카운트를 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, left = 0, right = 0, ans = 0;
  cin >> n >> m;
  deque<int> dq;
  for (int i = 1; i <= n; i++)
    dq.push_back(i);
  while (m--) {
    int x;
    cin >> x;
    for (int i = 0; i < dq.size(); i++) {
      if (dq[i] == x) {
        left = i;
        right = dq.size() - i;
      }
    }
    if (left <= right) {
      while (dq.front() != x) {
        dq.push_back(dq.front());
        dq.pop_front();
        ans++;
      }
      dq.pop_front();
    } else {
      while (dq.front() != x) {
        dq.push_front(dq.back());
        dq.pop_back();
        ans++;
      }
      dq.pop_front();
    }
  }
  cout << ans << '\n';
  return 0;
}