[C] 백준 - 1158번: 요세푸스 문제

7월 18일(화) - 자료 구조 (1158번)

1158번: 요세푸스 문제

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 저번주에 풀이했던 "10845번: 큐" 문제에서의 큐 자료구조를 활용하는 것을 예상

- 하지만 "11866번: 요세푸스 문제0"에서 풀이를 진행했던 경우와 마찬가지로

  선형 큐로 풀이를 진행하는 경우, dequeue할 때 마다 남아있는 값들의 위치를 다시 조절해주어야 함

- 따라서 원형 큐를 사용하기로 함

[C] 백준 - 10845번: 큐

[C] 백준 - 11866번: 요세푸스 문제0

 

- 원형 큐의 자료구조는 학교에서 사용한 교재와 아래의 사이트를 참고하여 작성

03 원형 큐 (Circular Queue) 자료 구조

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 수정 전
	printf("<");
	int count = 0;
	while (!empty())
	{
		count++;

		if (count % K == 0)
		{
			if (empty())
			{
				printf("%d", dequeue());
			}
			else
			{
				printf("%d, ", dequeue());
			}
		}
		else
		{
			enqueue(dequeue());
		}
	}
	printf(">");

// 수정 후
	printf("<");
	int count = 0;
	while (!empty())
	{
		count++;
		int target = dequeue();

		if (count % K == 0)
		{
			if (empty())
			{
				printf("%d", target);
			}
			else
			{
				printf("%d, ", target);
			}
		}
		else
		{
			enqueue(target);
		}
	}
	printf(">");

1. main 함수내에서 위와같이 작성하고 전체를 돌렸더니, <3, 6, 2, 7, 5, 1, 4, > 이렇게 잘못된 형식으로 출력되고있음

-> dequeue하는 대상을 지정하지 않고 바로바로 print하는 과정중에서 발생한 문제라고 판단

-> int target = dequeue()를 추가해주며 해결

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int circular_queue[5001];
int front = 0;
int rear = 0;

int N, K;

void enqueue(int x)
{
	circular_queue[(rear++) % N] = x;
}

int dequeue()
{
	if (rear - front + 1 == 0)
	{
		return -1;
	}
	else
	{
		return (circular_queue[(front++) % N]);
	}
}

int empty()
{
	if (front == rear)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int full()
{
	if ((rear++) % N == front)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	scanf("%d %d", &N, &K);

	for (int i = 1; i < N + 1; i++)
	{
		enqueue(i);
	}

	printf("<");
	int count = 0;
	while (!empty())
	{
		count++;
		int target = dequeue();

		if (count % K == 0)
		{
			if (empty())
			{
				printf("%d", target);
			}
			else
			{
				printf("%d, ", target);
			}
		}
		else
		{
			enqueue(target);
		}
	}
	printf(">");

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ