[C] 백준 | 2164번 코드 - 카드2

>문제

> 핵심

큐

>풀이과정

문제를 읽어보니,, 스택이나 큐를 사용해야 할 것 같다는 느낌이 왔다.

제일 위에 있는 값을 뽑아 제일 아래로 넣는 과정을 봤을때 큐가 더 적합하다는 생각에 큐로 풀었다. 선입선출!

 

근데 문제를 풀면서 두개의 난관이 있었다.

 

1. 50만칸이나 되는 배열 선언?

 

처음에는 main() 부분에 Queue를 만들어 사용하려 했다.

그런데 그 경우에는 다음과 같은 에러메세지가 뜬다.

C6262 에러

- 이 경고는 미리 설정된 임계값을 초과하는 스택 사용량이 함수에서 검색되었음을 나타냅니다. ~~ 문제를 해결하려면 일부 데이터를 힙 또는 다른 동적메모리로 이동할 수 있습니다.

 

그럼 우리는 50만칸짜리 배열을 결국 만들 수 없는것일까??

아니다.

 

지역변수가 아니라 전역변수에서 배열을 선언하면 50만칸짜리 배열도 사용할 수 있다!

또한, 동적할당을 이용해도 50만칸 짜리 배열을 만들어 사용할 수 있다.

#define SIZE 500001
typedef struct {
	int* queue;
	int front, rear;
}QueueType;

int main()
{
	QueueType Queue;
	Queue.queue = (int*)malloc(sizeof(int) * SIZE);
	
    return 0;
}

문제 해결!

 

2. 50만칸 배열을 선언했는데 왜 틀렸을까?

 

여기서 쓸데없이 좀 해맸다.

입력받는 수의 최대 개수가 50만개이므로 처음에는 50만칸짜리 원형 큐를 만들어서 풀었는데 자꾸 틀렸다고 뜨는거였다..  다른사람들 코드랑 로직도 동일하게 짰는데.. 왜지??

다른사람 코드 붙여넣어서 돌려보니 그제서야 뭔가 틀렸다는걸 알았다.

 

알고보니.. 500,000칸 이 아니라 최소 500,001칸의 배열이 필요한것이었다..

 

왜냐?

원형큐를 만들어 사용하고 있었는데, 큐가 비었는지 확인하는 is_full 를 만들어 사용하고 있었다.

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

이 is_full 함수에서, rear와 front 사이에 한칸의 빈칸이 있어야 하는데, 50만칸 배열에 50만개의 값을 다 채워넣으니 빈칸이 안남아있게 되고, 그래서 50만개의 값이 다 들어왔을때 정답이 나오지 않은것이다.....

 

결국 문제 해결!

 

남아있는 카드를 확인하는 알고리즘은 꽤나 간단하다.

 

1. 제일 위에 있는 값을 dequeue 해서 e 에 저장.

2. 큐가 비었으면? -> break

3. 제일 위에있는 값을 dequeue 해서 제일 밑으로 enqueue.

4, 위 과정을 큐가 다 비기 전까지 반복

 

5. 제일 마지막에 남아서 dequeue 된 e 값을 출력하면 끝!

 

>깨달은점

큐. 원형큐 알고리즘에 대해 다시한번 공부할 수 있었다.

기본부터 잘하자.. 제발!

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define SIZE 500001

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

QueueType Queue;

void Queue_init(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) % SIZE == q->front);
}

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

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

int main()
{
	Queue_init(&Queue);
	int i, n, e = 0;

	scanf("%d", &n);

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

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

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

	return 0;
}