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

4월 18일(화) - 큐, 덱  (11866번)

11866번: 요세푸스 문제 0

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

 

최초 생각 정리

- 1부터 N까지의 숫자는 push를 통해서 큐에 저장한다

- 그리고 큐의 사이즈가 0이 아닐경우를 조건으로 while문을 돌리며

  1) 1번째 숫자부터 K-1번째까지의 숫자들은 pop 그리고 그대로 다시 push를 해준다

  2) K번째 숫자는 pop해준 뒤, 나중에 출력을 위해 순서대로 저장할 배열 josephus에 저장해준다

- 최종출력은 배열 josephus를 N개 출력

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

 

문제점

// 수정 전 -> 직전 2164번 코드
	while (size() != 1)
	{
		pop();
		push(pop());
	}

// 수정 후 -> 11866번 코드
	int tmp;
	int j = 0;
	while (size() != 0)
	{
		for (int i = 1; i <= K - 1; i++)
		{
			tmp = pop();
			push(tmp);
		}
		tmp = pop();
		josephus[j] = tmp;
		j++;
	}

1. 직전 2164번과 동일하게 큐의 내용을 pop 그리고 push 해주는 과정이 필요하다

-> 1번째부터 K-1번째까지의 숫자들을 pop 그리고 push해주는 과정에서 이전에는 pop한 값을 다른 변수에 저장 x

-> 하지만 변수 tmp를 이용하는 것이 더 직관적이라서 수정

-> K번째 숫자를 pop한 뒤, 새로운 배열인 josephus에 저장하는 과정에서도 변수 tmp 사용하는 것으로 수정

 

2. 최종출력을 위해서 숫자들을 차례로 저장해야할 배열인 josephus의 인덱스값을 어떻게 증가시킬지 고민

-> 그냥 int j=0을 하나 새롭게 선언하고, j++로 증가시키는 것으로 설정

 

int queue[1000000];
int front = 0;
int rear = -1;

int josephus[1001];

3. 직전 2164번 문제에서도 queue 범위의 크기 때문에 런타임 에러가 발생했었기 때문에 신경 쓰고자했다

-> 적당히 queue[ 5000 ] 정도로 설정했지만, 또 다시 런타임 에러(OutOfBounds) 가 발생

-> queue의 범위를 1000 x 1000으로 수정

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

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int queue[1000000];
int front = 0;
int rear = -1;

int josephus[1001];

void push(int x)
{
	queue[++rear] = x;
}

int pop()
{
	if (rear - front + 1 == 0)
	{
		return -1;
	}
	else
	{
		return (queue[front++]);
	}
}

int size()
{
	return (rear - front + 1);
}

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

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

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

	int tmp;
	int j = 0;
	while (size() != 0)
	{
		for (int i = 1; i <= K - 1; i++)
		{
			tmp = pop();
			push(tmp);
		}
		tmp = pop();
		josephus[j] = tmp;
		j++;
	}
	
	printf("<");
	for (int i = 0; i < N - 1; i++)
	{
		printf("%d, ", josephus[i]);
	}
	printf("%d>", josephus[N - 1]);
	return 0;
}

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