[C] 백준 | 1966번 코드 - *프린터 큐

>문제

> 핵심

큐

>풀이과정

이 문제를 풀다가 돌아버릴 뻔 했다.

문제를 풀고 나니 모두 나의 무지에 의한 것이였다.

 

내가 겪었던 문제점

 

1. 내가 원하는 문서가 언제 출력되는지 어떻게 알아?

큐의 front에 있는 값이 현재 큐에서 가장 중요도가 높은 문서라면 dequeue를 진행하고,

그렇지 않다면 dequeue 후 맨 뒤에 enqueue 한다.

 

근데 처음에 m번째 위치에 있는 문서가 enqueue, dequeue를 거치며 순서가 뒤죽박죽 섞이는데 언제 출력될지 어떻게 알까..?

곰곰이 생각하다가,, int[SIZE][2] 배열을 쓸까 생각하다가 이건 큐로 만들기 조금 복잡할 것 같아서 구조체! Paper을 만들어서 구조체 배열을 갖는 큐를 만드는 방식을 사용했다.

 

Paper 구조체에 중요도를 넣는 key변수와 내가 찾고자 하는 문서를 가리키는 value변수를 선언했다.

그리고 내가 찾고자 하는 문서의 value값은 1, 그 이외의 문서는 0으로 넣도록 했다.

 

처음에 값을 enqueue할 때, 내가 찾고자 하는 문서의 value값을 1으로 넣고,

위의 IsLarge함수를 돌면서 큐의 선두에 제일 높은 중요도를 갖는 문서가 오게 세팅하고 dequeue 와 cnt+=1

이때 dequeue된 값의 value가 1이라면 내가 찾고자하는 문서가 출력된것이므로 break 후 cnt 출력!

 

그래서 이 문제는 대충 해결했다!

 

2. 원형큐 탐색..

내가 치명적인 실수를 하고있었다...

일반적인 큐는 front < rear 꼴을 갖는게 일반적인데

원형 큐는 끝이 없이 원형으로 돌기때문에 front > rear 이 될 가능성이 있다는 것이다...!!!!!!!

 

int IsLarge(QueueType* q)
{
	if (IsEmpty(q))
		return -1;

	int idx = (q->front + 1) % SIZE;
	int max = q->queue[idx].key;

	while(idx <= q->rear)
	{
		if (max < q->queue[idx].key)
			return 1;
		idx = (idx + 1) % SIZE;
	}
	return 0;
}

이 코드 왜 틀렸을까?

인덱스가 (q->front + 1) % SIZE 부터 시작해서 q->rear까지 탐색하면서 중요도가 높은게 있는지 확인하는 함수인데,

바로 front > rear 가 될 가능성을 고려하지 않았기 때문이다......................................... 으악!

 

front > rear이라면 저 반복문을 한번도 돌지않고 return 0을 찍어버리기 때문에 내가 원하는대로 동작하지 않았던것..

그래서 큐 구조체에 q->size변수를 추가해서 enqueue할 때마다 size++, dequeue할 때마다 size-- 하는걸로 바꿔서,

큐의 사이즈만큼 큐를 한바퀴 도는걸로 수정했다..

int IsLarge(QueueType* q)
{
	if (IsEmpty(q))
		return -1;

	int idx = (q->front + 1) % SIZE;
	int max = q->queue[idx].key;

	for (int i = 0; i < q->size - 1 ; i++)
	{
		idx = (idx + 1) % SIZE;
		if (max < q->queue[idx].key)
			return 1;
	}
	return 0;
}

 

그러니까 결국 정답이 나왔다..

 

내가 해맨건 결국 나의 원형 큐에 대한 이해부족에서 나왔다..

원형 큐,, 이번에 크게 배웠으니 다음엔 잘 써먹을 수 있을 것 같다.

 

>깨달은점

원형큐의 개념을 똑바로 좀 알자

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define SIZE 101

typedef struct
{
	int key;
	int value;
}Paper;

typedef struct
{
	Paper queue[SIZE];
	int front, rear;
	int size;
}QueueType;

void InitQueue(QueueType* q)
{
	q->front = q->rear = 0;
	q->size = 0;
}

int IsEmpty(QueueType* q)
{
	return q->rear == q->front;
}

int IsFull(QueueType* q)
{
	return (q->rear + 1) % SIZE == q->front;
}

void Enqueue(QueueType* q, Paper e)
{
	if (IsFull(q))
		return;

	q->rear = (q->rear + 1) % SIZE;
	q->queue[q->rear] = e;
	q->size += 1;
}

Paper Dequeue(QueueType* q)
{
	if (IsEmpty(q))
		exit(1);

	q->front = (q->front + 1) % SIZE;
	q->size -= 1;
	return q->queue[q->front];
}

void PrintQueue(QueueType* q)
{
	int idx = (q->front + 1) % SIZE;

	for (int i = 0; i < q->size;i++)
	{
		printf("[%d %d] ", q->queue[idx].key, q->queue[idx].value);
		idx = (idx + 1) % SIZE;
	}
	printf("\n");
}

int IsLarge(QueueType* q)
{
	if (IsEmpty(q))
		return -1;

	int idx = (q->front + 1) % SIZE;
	int max = q->queue[idx].key;

	for (int i = 0; i < q->size - 1 ; i++)
	{
		idx = (idx + 1) % SIZE;

		// Front값 중요도보다 높은게 있으면.. return 1
		if (max < q->queue[idx].key)
			return 1;
	}
	
	// Front값 중요도가 제일 높으면.. return 0
	return 0;
}

int main()
{
	QueueType q; 
	Paper tmp;
	int i, j, n, m, e, test_case, cnt;

	scanf("%d", &test_case);

	for (i = 0; i < test_case; i++)
	{
		scanf(" %d  %d", &n, &m);

		// 삽입 전 큐 초기화
		InitQueue(&q);
		cnt = 0;

		// 큐에 데이터 삽입
		for (j = 0; j < n; j++)
		{
			scanf(" %d", &tmp.key);
			
			// 내가 찾고자 하는 값은 1로 세팅
			if (j == m)
				tmp.value = 1;
			// 나머지는 0으로 초기화.
			else
				tmp.value = 0;

			Enqueue(&q, tmp);
		}

		do
		{
			// 제일 중요한게 맨앞에 올때까지 
			while (IsLarge(&q) != 0)
			{
				tmp = Dequeue(&q);
				Enqueue(&q, tmp);
			}
			//PrintQueue(&q);
			tmp = Dequeue(&q);
			cnt += 1;
		} while (tmp.value != 1);

		printf("%d\n", cnt);
	}

	return 0;
}