백준(baekjoon) [C] - 1966번: 프린터 큐

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

---

#include <stdio.h>  // 프린터 큐
#include <stdlib.h>

typedef struct
{
	struct node* next;
	int data;
	int idx;
}node;

typedef struct
{
	node* rear;
	node* front;
	int count;
}queue;

void init_queue(queue* q)
{
	q->front = q->rear = NULL;
	q->count = 0;
}

int is_empty(queue* q)
{
	return q->count == 0;
}

void push(queue* q, int data, int idx)
{
	node* newnode = malloc(sizeof(node));
	newnode->data = data;
	newnode->idx = idx;
	newnode->next = NULL;

	if (is_empty(q))
		q->front = newnode;
	else
		q->rear->next = newnode;
	q->rear = newnode;
	q->count++;
}

node pop(queue* q)
{
	node* ptr;
	node temp;
	if (is_empty(q))
		return;
	ptr = q->front;
	temp.data = ptr->data;
	temp.idx = ptr->idx;
	q->front = ptr->next;
	free(ptr);
	q->count--;

	return temp;
}

int FRONT(queue* q)
{
	return q->front->data;
}

int compare_(void* first, void* second)
{
	int* a = first;
	int* b = second;
	if (*a > *b)
		return -1;
	else if (*a < *b)
		return 1;
	else
		return 0;
}


int main()
{
	int t;
	scanf("%d", &t);

	int arr[100];
	for (int i = 0; i < t; i++)
	{
		int ans = 1, max = 0;

		queue q;
		init_queue(&q);

		int n, m;
		scanf("%d %d", &n, &m);
		for (int j = 0; j < n; j++)
		{	
			scanf("%d", &arr[j]);
			// 큐에 가중치 및 m값 저장하기
			if (j == m)
				push(&q, arr[j], m);
			else
				push(&q, arr[j], -1);
		}
		qsort(arr, n, sizeof(int), compare_);

		int k = 0;
		while (1)
		{
			node temp = pop(&q);
			if (arr[k] == temp.data)
			{
				if (temp.idx == m)
					break;
				k++;
				ans++;
			}
			else
			{
				// 뒤로 보내기
				push(&q, temp.data, temp.idx);
			}
		}
		printf("%d\n", ans);
	}

	return 0;
}

---

MEMO

-- 큐에 가중치와 알고 싶은 인덱스인 m을 push(원하는 인덱스가 아닌 경우 구분하기 위해서 -1로 push)

--  가중치값 내림차순 정렬 --> 가장 큰 값들을 우선적으로 pop해주고 아닌 값들은 큐의 rear로 보내주기 위해서

-- while문이 핵심 --> 가장 큰 가중치인 경우이면서 원하는 인덱스이면 stop(문제의 조건 만족), 하지만 원하는 인덱스가 아니라면 이전에 pop을 이미 했으니(인쇄한 경우) 결과값 증가, k값 증가(그 다음 큰 가중치로 설정)

-- 가장 큰 값이 아닌 경우 해당 가중치는 큐의 뒤로 보내기

 

!! 생각보다 시간이 오래 걸린 문제.. !!