프린터_우선순위_queue

/*
	1. 큐의 가장 앞에 있는 문서의 중요도 확인
		if 가장 앞이 있는 문서의 중요도가 가장 크다
			인쇄
		else
			큐의 맨 뒤로 보낸다.
		모든 큐의 중요도가 인쇄되면 끝난다

	문제
		큐의 문서의 수(n)과 중요도(m)이 주어졌을 때,
		어떤 한 문서가 몇 번쨰로 인쇄되는지 알아내는 것

	입력
	testcase = 실행하는 계산식의 횟수
	n = 문서의 수
	m = 몇 번쨰로 인쇄되었는지 궁금한 문서가 큐의 어떤 위치에 있는지 알려주는 수
	
	중요도는 1~9 까지 이다.
	문서의 수 1~100 까지 이다.
	m은 0~n 까지 이다.

	계산식
	일반 배열 큐
	m의 위치를 알 수 있는 배열 큐
	
	선형 큐 구현
	다른 특징
	1) 큐의 front에 있는 값이 제일 클 경우만 삭제
		만약, 아니면
			모든 값을 앞으로 땡겨서 
			반복한다.

	중요도 출력함수(중요도 값 num, 중요도의 위치 loc)
		반복 
			if (num == 반복되는 문서[i] && loc == 1)
				break;
			count++;
		return count;
		

	int main(){
		2개의 배열 생성
			1. 문서의 중요도를 받는 큐
			2. 몇 번째로 인쇄되었는지 궁금한 문서의 위치를 가리키는 큐
				예) (0,0,1,0)

	}
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

typedef int element;
typedef struct {
	int front;
	int rear;
	element data[MAX_SIZE];
} queuetype;

void init_queue(queuetype *q) {
	q->front = -1;
	q->rear = -1;
}

void init_ipt_loc(queuetype *ipt_loc, int n) {
	for (int i = 0; i <= n; i++)
	{
		ipt_loc->data[i] = 0;
	}

	ipt_loc->front = -1;
	ipt_loc->rear = n - 1;
}

void queue_attach_ipt_loc(queuetype *ipt_loc, int n) {
	ipt_loc->data[n] = 1;
}

int underflow(queuetype *q) {
	return (q->rear - 1 == q->front);
}

int overflow(queuetype *q) {
	return (q->rear == MAX_SIZE - 1);
	}

int queue_attach(queuetype *q, int n) {
	if (overflow(q) == 1)
		return 0;

	q->data[++(q->rear)] = n;
	return 1;
}

int dequeue(queuetype *q) {
	if (underflow(q) == 1)
		return 0;
	++(q->front);
	return 1;
}

void queue_printf(queuetype *q)
{
	for (int i = 0; i <= q->rear; i++)
	{
		if (i > q->front)
			printf("%d ", q->data[i]);
	}
}

void queue_change(queuetype *q) {
	int frist = q->data[q->front + 1];

		for (int i = q->front + 1; i < q->rear; i++)
		{
			q->data[i] = q->data[i + 1];
		}
		q->data[q->rear] = frist;
}


int bew(queuetype *q, int n) {
	int num = q->data[q->front + 1];
	int cnt_over = 0;
	int cnt_ = 0;
	int cnt_under = 0;

	for (int i = q->front + 1; i <= q->rear; i++)
	{
		if (num > q->data[i])
			cnt_over++;
		if (num == q->data[i])
			cnt_++;
		if (num < q->data[i])
			cnt_under++;
	}

	if ((cnt_over + cnt_ == n) || (cnt_over + cnt_ == n))
		return 0;
	else if (cnt_ == q->rear + 1)
		return 0;
	else if (cnt_under >= 1)
		return 1;
}


int main()
{
	int testcase = 0;
	queuetype ipt_loc;
	queuetype file;
	int n, m;
	int num;
	int count = 0;

	scanf_s("%d", &testcase);

	for (int i = 0; i < testcase; i++)
	{
		scanf_s("%d %d", &n, &m);
		init_ipt_loc(&ipt_loc, n);
		init_queue(&file);
		count = 0;

		for (int j = 0; j < n; j++)
		{
			scanf_s("%d", &num);
			if (m == j) {
				queue_attach_ipt_loc(&ipt_loc, j);
			}
			queue_attach(&file, num);
		}
	
		while (count >= 0)
		{
			if (bew(&file, n) == 1) {
				queue_change(&file);
				queue_change(&ipt_loc);
			}
			else if (bew(&file, n) == 0) {
				count++;
				n--;
				if (ipt_loc.data[ipt_loc.front + 1] == 1) 
				{
					printf("%d\n", count);
					count = -1;
				}
				dequeue(&file);
				dequeue(&ipt_loc);
			}
		}
	}
}