1966 프린터 큐

queue를 만들고,

4 2

1 2 3 4

n = 4, m = 2, cnt = 0

2 3 4 1        m = 1

3 4 1 2        m = 0

4 1 2 3        m = 3

1 2 3           m = 2, cnt = 1

2 3 1           m = 1

3 1 2           m = 0

1 2             cnt = 2

---

6 0
1' 1 9 1 1 1
n = 6, m = 0, cnt = 0

1 9 1 1 1 1'     m = 5
9 1 1 1 1' 1     m = 4
1 1 1 1' 1       m = 3, cnt = 1
1 1 1' 1          m = 2, cnt = 2
1 1' 1            m = 1, cnt = 3
1' 1              m = 0, cnt = 4
1                 cnt = 5

 

 

max 값 있으면
    max 값을 pop 할 때까지
        front를 pop하고 push함
        m 인덱스 갱신
    cnt++

 

max 값 없으면
    m 값 pop할 때 까지
        if (front가 m값과 같으면)
            pop(), cnt++
        else
            front를 pop(), push()

 

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    while(T--){
        int N, M, M_value, p, ans = 0;
        scanf("%d %d", &N, &M);
        queue<int> q;
        for (int i=0; i<N; i++) {
            scanf("%d", &p);
            if (i == M) M_value = p;
            q.push(p);
        }

        while(1){
            queue<int> temp = q;
            int qsize = temp.size();
            int max = M_value;
            int max_idx = M;
            for (int i=0; i<qsize; i++) {
                if (temp.front() > max) {
                    max_idx = i;
                    max = temp.front();
                } 
                temp.pop();
            }
            // printf("%d %d\n", max_idx, max);
            if (max != M_value){
                for (int i=0; i<=max_idx; i++){
                    if (M == 0) M = q.size() - 1;
                    else M--;

                    if (q.front() == max) q.pop();
                    else {
                        q.push(q.front());
                        q.pop();
                    }
                }
                ans++;
            }
            else {
                for (int i=0; i<=M; i++){
                    if (q.front() == M_value){
                        q.pop();
                        ans++;
                    }
                    else {
                        q.push(q.front());
                        q.pop();
                    }
                }
                break;
            }
        }
        printf("%d\n", ans);
    }
    
    return 0;
}