BOJ 1021] 회전하는 큐

문제 바로가기

[ 접근 법 ]

- 앞, 뒤로 push, pop이 가능하다는 점에서 deque를 사용하면 쉽게 접근할 수 있다.

- 문제의 핵심은 언제 2번 혹은 3번을 진행하는지 판단해야한다는 것이다.

 

{2번 혹은 3번 중 파악하기}

- 먼저, 구하려는 수가 deque에서 몇 번째에 위치하는 지 파악해야한다. (deque에서 원하는 숫자를 pop하게 되면 길이가 바뀌기 때문)

- for문을 통해 구하려는 값이 몇번에 있는지 구한다.

- 만약 ( deque의 size - 구하려는 수의 위치 > 구하려는 수의 위치 )이면 3번보다 2번이 효율적이다.

- 반대로 ( deque의 size - 구하려는 수의 위치 <= 구하려는 수의 위치 )이면 2번보다 3번이 효율적이다.

- 위에 둘중 하나를 2번 혹은 3번을 선택 후, while문을 통해 구하려는 수가 front에 위치하도록 한다.

- deque의 front와 구하려는 수가 같으면 pop_front를 한다.

 

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;


int n, m, tmp, cnt=0;
deque<int> dq;
queue<int> seq;

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        cin >> tmp;
        seq.push(tmp);
    }
    for (int i = 1; i <= n; i++) {
        dq.push_back(i);
    }

    while (!dq.empty() && m--) {

        for (int i = 0; i < dq.size(); i++) {
            if (dq[i] == seq.front()) {
                tmp = i;
                break;
            }
        }


        // 찾고자하는 것의 위치를 구함
        // 전체 사이즈 - 그 위치 > 그 위치 // 앞으로
        // else면 그 뒤로 
        //cout << dq.front() << " , " << seq.front() << endl;

        if (dq.size() - tmp > tmp) {
            while (dq.front() != seq.front()) {
                tmp = dq.front();
                dq.push_back(tmp);
                dq.pop_front();
                cnt++;
            }
            if (dq.front() == seq.front()) {
                dq.pop_front();
                seq.pop();
            }
        }
        else {
            while (dq.front() != seq.front()) {
                tmp = dq.back();
                dq.push_front(tmp);
                dq.pop_back();
                cnt++;
            }
            if (dq.front() == seq.front()) {
                dq.pop_front();
                seq.pop();
            }
        }



    }


    cout << cnt;

    return 0;
}