백준 : 1158번, 요세푸스 문제

문제 주소 : www.acmicpc.net/problem/1158

정답 비율 : 49.170% (2021.02.12 12:54 기준)

1158번: 요세푸스 문제

 

문제 요약 : 

X

 

문제 조건 :

입력 : n과 k를 빈칸을 사이에 두고 주어집니다. n과 k는 1 ~ 5000 사이의 숫자이며 k는 n 이하입니다.

출력 : <3, 6, 2, 7, 5, 1, 4> 이 처럼 출력을 하면 됩니다.

시간 : 2초

 

문제 풀이 :

문제를 보면서 가장 먼저 떠오른 것은 queue(FIFO : First In First Out)을 사용하는 것이었습니다. 

enqueue의 조건은 초기 1 ~ n을 추가하고 dequeue 한 횟수 % k 한 값이 0이 아닐 경우에만 수행합니다.dequeue의 조건은 초기 1 ~ n을 추가한 상태에서 queue가 empty가 될 때까지 dequeue를 수행합니다.

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

int que[5000];
int n, k, front = 0, rear = 0;

void enqueue(int data)
{
	que[rear++ % n] = data;
}

int dequeue()
{
	return que[front++ % n];
}

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

int main()
{
	int i = -1, c = 0;

	scanf("%d %d", &n, &k);

	for (i = 1; i <= n; i++)
		enqueue(i);

	printf("<");
	while (!is_empty())
	{
		int val = dequeue();
		c++;
		if (c % k == 0)
		{
			if (is_empty()) //last data
				printf("%d", val);
			else
				printf("%d, ", val);
		}
		else
		{
			enqueue(val);
		}
	}
	printf(">");

}

-> 선형 큐를 배열로 구현할 경우 dequeue과정에서 데이터를 재 정렬하는 과정이 필요합니다. 따라서 시간 초과가 발생할 거라고 판단되어 링크드 리스트로 선형 큐를 구현해야 합니다. 하지만 그 과정은 귀찮고 무엇보다 n의 최대 크기가 5000이므로 큐의 최대 크기를 알 수 있습니다. 따라서 순환 큐로 해당 문제를 풀었습니다.

-> n의 크기가 5000으로 크기 않으므로 front과 rear 값을 0 ~ n - 1 사이 값을 순환하는 것인 아닌 계속 증가하는 방식을 사용하였습니다.

 

Python3

#solve 1158

c = 0
n, k = list(map(int, input().split()))
que = [i for i in range(1, n + 1)]
ans = []

while len(que):
    c = (c + k - 1) % len(que)
    ans.append(que.pop(c))
    
print('<', str(ans)[1:-1], '>', sep='')

-> list를 queue형태로 사용하여 문제를 풀었습니다. 

-> C언어처럼 일일이 enqueue, dequeue를 수행하면 시간 초과되었습니다. 따라서 다른 방식을 사용하였습니다. 바로 index의 범위는 0 ~ len(que) - 1이고 현재 index에서 k - 1 만큼 증가한 index는 pop을 진행하므로 (index + k - 1) % len(que)를 통하여 한번에 출력할 index를 구할 수 있게 됩니다.

 

해당 문제를 python으로 작성하면서 처음으로 '오!! 굉장히 파이썬 다운 코드다.'라는 느낌을 받았습니다.(파이썬 초보의 개인적 감으로 ㅎㅎㅎ)