[백준 1021번] 회전하는 큐

---

문제 화면

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

문제 풀이

이 문제는 deque의 자료구조를 응용하는 문제이다. 자료구조를 익히는 기본적인 문제이지만 문제 이해를 잘못해서 한참을 삽질했다. (-.-)

핵심은 deque의 인덱스 기능을 활용해 찾고자 하는 요소가 현재 몇번째 인덱스의 요소인지 찾아내고 왼쪽 오른쪽 중에 어느쪽으로 돌리는게 더 빠른지를 결정해서 왼쪽이나 오른쪽으로 돌리는 횟수의 합을 구하는 문제이다. 참고로 deque의 한 중간에 있는 요소라면 오른쪽이 아닌 왼쪽으로 돌려야 정답이 뜬다. 오른쪽으로 돌리도록 구현하면 마지막 테스트케이스에서 오답이 뜬다(이것도 문제에 명시되면 좋을거 같다).

제출 코드

#include <iostream>
#include <deque>

using namespace std;

deque<int> d;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, a, idx, ans=0;

    cin >> n >> m;

    for(int i = 1 ; i <= n ; i++) d.push_back(i);

    for(int i = 0 ; i < m ; i++) {
        cin >> a;
        for(int j = 0 ; j < d.size() ; j++) {
            if(a==d[j]) { // deque의 인덱스 기능을 활용하는게 문제의 핵심이다. d.at(i)도 가능하지만 이게 더 빠르다. 차이는 아래 링크 확인 
                idx = j; 
                break;
            }
        } // 입력받은 숫자가 현제 deque에서 어디 인덱스인지 확인

        if(idx<=d.size()/2) { // 찾고자 하는 숫자가 deque의 왼쪽에 더 가까운 케이스
            while(d.front()!=a) {
                d.push_back(d.front());
                d.pop_front();
                ans++; // 왼쪽으로 한번 돌릴 때마다 ++
            }
        } 

        else { // 찾고자 하는 숫자가 deque의 오른쪽에 더 가까운 케이스
            while(d.front()!=a) {
                d.push_front(d.back());
                d.pop_back();
                ans++; // 오른쪽으로 한번 돌릴 때마다 ++
            }
        } 
        d.pop_front();

    }

    cout << ans;


    return 0;
}

결론

Deque에 최적화된 문제이고 stack이나 queue와 달리 deque는 인덱스 기능이 있다는 것을 배워갈 수 있는 문제이다. 다음부터는 문제를 꼼꼼하게 읽어서 삽질하지 말자.

출처

• https://blockdmask.tistory.com/73