(백준/C++) 1021번_회전하는 큐

1021번: 회전하는 큐 (acmicpc.net) 문제는 양방향 큐인 덱(Deque)을 이해하고 나서, 덱(Deque)으로 원하는 요소를 빼낼 수 있는 최소한의 횟수를 찾아내면 되는 문제입니다.

좀 더 설명하자면, 원하는 요소를 찾을 때까지 요소들을 이동시키고, 원하는 요소를 찾으면 해당 요소를 빼내는데, 최소한의 횟수만으로 빼내야 하는 문제입니다.

이 문제는 원하는 내용이 간단한 만큼 아이디어를 쉽게 떠올릴 수 있으리라 생각됩니다.

주의사항

이 문제에서 주의해야 할 점은 하나인 것 같습니다.

문제에서 요소를 빼낼 수 있는 위치가 덱(Deque)의 제일 앞 요소만 빼낼 수 있다는 점입니다.

즉, 원하는 Target 요소를 제일 뒤에 배치했다고 해도 앞에서만 뺄 수 있기 때문에 한 번 더 오른쪽으로 밀어 앞에서 뺄 필요가 있다는 점입니다.

(10 3 / 2 9 5 문제에서 2 9 5 요소를 빼낼 때, 제일 앞이나 제일 뒤에 배치하는 최소한의 횟수는 6회지만, 앞에서만 빼낼 수 있기 때문에 8회가 정답입니다.)

풀이 과정

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N, M, count = 0;
    deque<int> list;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        list.push_back(i);
 
    while(M--)
    {
        int target;
        cin >> target;
 
        int left = find(list.begin(), list.end(), target) - list.begin(); // 원하는 값 위치 찾기
        int right = list.size() - left;
 
        // 이동 구현
        if(left < right)
        {
            while (left--)
            {
                list.push_back(list.front());
                list.pop_front();
                count++;
            }
            list.pop_front();
        }
        else // (left >= right)
        {
            while (right--)
            {
                list.push_front(list.back());
                list.pop_back();
                count++;
            }
            list.pop_front();
        }
    }
    cout << count;
}

<iterator>는 여러가지 연산을 지원합니다.
여기에서 iterator - iterator 를 사용하는 것으로 iterator간의 차이를 index 혹은 left 값으로 이용했습니다.
iterator에 대한 더 많은 자료는 다음 사이트에서 확인하실 수 있습니다.

https://cplusplus.com/reference/iterator/

부록: <Iterator> 가 가질 수 있는 유효한 표현식

출처: https://cplusplus.com/reference/iterator/