[백준][C] 2164-카드2/원형 큐/QUEUE

[2164] - 카드 2

 

 

 

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

2164번: 카드2

 

❕ 접근

문제 설명이 약간 복잡해서 처음엔 겁먹었는데 막상 풀어보니까 정말 큐만 쓰는 문제였다. 

선형 큐보다는 아무래도 원형 큐가 훨씬 효율적일 것 같아 원형 큐로 접근하기로 했다.

 

👏 구현

 

1. 입력을 받으며 원형 큐에 N까지의 수를 enqueue

2. 원형 큐에 카드가 다 없어질때까지 dequeue 한 번, dequeue -> enqueue 한번 수행한다.

 

*총 dequeue는 두번이며 두번째 dequeue한 카드는 중간 값에 저장해 enqueue로 다시 위에 추가해준다.

 

🙆 코드

 

#include <stdio.h>
#include <stdlib.h>
#define MAX 500001


typedef int element;
typedef struct {
	element data[MAX];
	int front, rear;
}QueueType;

void error(char* message) {
	printf("%s\n", message);
	exit(1);
}
//초기화
void init_queue(QueueType* q) {
	q->front = q->rear = 0;

}
//공백 상태 검출 함수
int is_empty(QueueType* q) {
	return (q->front == q->rear);
}

//포화 상태 검출 함수
int is_full(QueueType* q) {
	return ((q->rear + 1) % MAX == q->front);
}

//원형 큐 출력 함수 
void queue_print(QueueType* q) {
	printf("QUEUE(front=%d rear=%d", q->front, q->rear);
	if (!is_empty(q)) {
		int i = q->front;
		do {
			i = (i + 1) % MAX;
			printf("%d | ", q->data[i]);
			if (i == q->rear)
				break;
		} while (i != q->front);
	}
	printf("\n");
}

//삽입함수
void enqueue(QueueType* q, element item) {
	if (is_full(q)) {
		error("포화상태임");
	}
	else
		q->rear = (q->rear + 1) % MAX;
	q->data[q->rear] = item;
}

//삭제 함수 
element dequeue(QueueType* q) {
	if (is_empty(q)) {
		error("공백상태임");
	}
	else
		q->front = (q->front + 1) % MAX;
	return q->data[q->front];
}

//카드 함수
void card(QueueType* q) {
	int tmp;

	while ((q->front + 1) % MAX != q->rear % MAX) {
		dequeue(q);
		tmp = dequeue(q);
		enqueue(q, tmp);
	}

	printf("%d", q->data[q->rear]);
}

int main(void) {
	QueueType queue;
	int n;

	init_queue(&queue);
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		enqueue(&queue, i + 1);
	}

	card(&queue);

	return 0;
}

 

👩‍💻 새롭게 알게된 점

 

1) 원형 큐에서는 원형 큐의 인덱스가 원형으로 돌아가며 사용해야하므로 %MAX 가 중요 !!

 

👌 느낀 점

 

1) 원형 큐의 포화상태는 한 칸이 비어있는 상태이므로 한 칸이 더 필요하다

-> MAX를 500001로 설정하는 거 까묵지 않기.