[스택 & 큐] 백준 2164번 (C언어) - 카드2

문제는 카드의 순서를 가장 위와 가장 아래에서만 조작하는 것이 특징이다. 그래서 처음 생각했던 것은 스택이었으나, 후입선출인 스택보단 선입선출이 되는 큐가 좀 더 효율적일 것 같아 큐로 하기로 했다.

 

큐를 만드는 방식에는 여러 종류가 있는데 대표적으로는 선형 큐, 원형 큐, 연결 큐가 있다. 덱도 있지만 이는 연결 큐의 일종인 것 같아 넣지 않았다. 

문제를 보니 가장 앞의 카드를 빼고 그다음에 오는 카드를 가장 뒤로 보내는 방식을 봤을 때 원형 큐가 가장 적합한 것 같았다. 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 500001

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

queue Queue;

void Queue_init(queue* q)
{
	q->front = q->rear = 0;
}

int is_empty(queue* q)
{
	return (q->front == q->rear);
}

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

void enqueue(queue* q, int e)
{
	if (is_full(q))
		return;
	q->rear = (q->rear + 1) % SIZE;
	q->queue[q->rear] = e;
}

int dequeue(queue* q)
{
	if (is_empty(q))
		return -1;
	q->front = (q->front + 1) % SIZE;
	return q->queue[q->front];
}

int main()
{
	Queue_init(&Queue);
	int num, last = 0;

	scanf("%d", &num);

	for (int i = 0; i < num; i++)
	{
		enqueue(&Queue, i + 1);
	}

	while (!is_empty(&Queue))
	{
		last = dequeue(&Queue);
		if (is_empty(&Queue))
			break;
		last = dequeue(&Queue);
		enqueue(&Queue, last);

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

	return 0;
}

먼저 MAX_SIZE같은 경우에는 50만까지의 정수를 받을 수 있기 때문에 크기는 인덱스를 고려하여 +1을 하여 설정해 주었다. 그다음은 많이 본 원형 큐의 기본적인 기능들인데 원형 큐에서 가장 중요한 것은 뭐니 뭐니 해도 (q->front + 1) % SIZE와 (q->rear + 1) % SIZE이다. 이 연산을 가볍게 설명하자면 그냥 앞으로 한 칸 움직이는 것인데 이렇게 거창하게 하는 이유는 front나 rear가 배열의 가장 끝에 도달했을 때, 다시 0번 인덱스로 가게 하기 위해서 쓰인다.

즉, 원형이라는 개념을 만들어주기 위해서 위 식을 도입하는 것이다. 

 

main함수에서는 queue를 생성하고, num만큼 큐의 배열에 저장해준다.

 다음 반복문에서 배열 안에 원소가 없어질 때까지 반복한다.

먼저, 마지막에 남을 숫자를 last라고 정하고, 이를 처음으로 삭제하는 원소로 지정한다. 이유는 num이 1이면 애초에 큐에 숫자가 하나밖에 없기 때문에 처음으로 삭제하는 숫자가 마지막으로 남은 숫자가 되기 때문이다. 

그래서 그다음에 if문을 넣어서 배열이 비어있으면 반복을 중지시킨다.

if문이 끝난 다음에는 문제에 제시된 대로 과정을 수행한다. 그 밑에 있는 원소를 삭제하고 다시 삽입하여 가자 뒤로 옮긴다. 이를 반복하면 언젠가는 마지막으로 남는 last가 생길 것이다.