[백준] 1021 회전하는 큐

 

풀이

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


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n, m;
    cin >> n >> m;

    deque<int> dq;

    for (int i = 1; i <= n; i++) {
        dq.push_back(i);
    }

    int ans = 0;

    while (m--) {
        int t;
        cin >> t;
        int idx = find(dq.begin(), dq.end(), t) - dq.begin();
        while(dq.front() != t) {
            if (idx < dq.size() - idx) {
                dq.push_back(dq.front());
                dq.pop_front();
            } else {
                dq.push_front(dq.back());
                dq.pop_back();
            }
            ans++;
        }
        dq.pop_front();
    }

    cout << ans;

    return 0;
}

 

문제에서 주어진 조건을 생각해보자. `1 2 3 4 5 ... n` 라는 줄이 있다고 가정 하고 m번 동안, 찾고자 하는 숫자를 뽑아내야한다.

숫자를 뽑아내는 규칙은 다음과 같다.

1. 맨 앞에 있는 숫자만 꺼낼 수 있다.
2. 줄을 회전시키는게 가능하다.
   • 왼쪽으로 한 칸 돌리기: 맨 앞이 뒤로 감
     • 예) 1 2 3 4 → 2 3 4 1
   • 오른쪽으로 한 칸 돌리기: 맨 뒤가 앞으로 옴
     • 예) 1 2 3 4 → 4 1 2 3
3. 최소로 돌려서 원하는 숫자를 앞에 가져온 다음 꺼내야 한다.
4. 돌린 횟수를 다 합쳐서 출력한다(최소값으로)

이 내용을 코드로 구현하면 문제를 해결할 수 있다.

 

하나 고려할점은 찾고자하는 타겟의 위치에 따라 왼쪽과 가까우면 2번 연산이, 오른쪽과 가까우면 3번 연산이 최소값을 구할 수 있는 방법인것을 염두해야한다.