문제 링크 : https://www.acmicpc.net/problem/1158

입력으로 사람의 수와 제거할 순번이 주어지고, 이에 따른 요세푸스 순열을 출력하는게 문제이다.

문제 해결 과정 1. 선형 큐

큐의 맨 앞 원소를 dequeue한 뒤에, 큐의 rear에 euqueue한다. 그러다가 k의 배수번째에 해당하면 원소를 dequeue한다. 이 때
큐가 빌 때까지 해당 과정을 반복한다. 제거된 원소는 새로운 배열 혹은 리스트에 append한다. 이 과정을 큐가 모두 빌 때 까지 반복한다.

코드 (C++)

STL stack을 사용함

// 언어 c++, 메모리 1228KB, 시간 144ms
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;


int main(void)
{
	queue<int> q;
	int n, k;
	int idx = 0;
	int number;
	int res[5000];
	int i = 0;
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++)
	{
		q.push(i);
	}

	while (q.size() != 0)
	{
		idx += 1;
		number = q.front();
		q.pop();
		if (idx % k == 0)
		{
			res[i++] = number;
		}
		else
		{
			q.push(number);
		}
	}
	printf("<");
	for (int i = 0; i < n-1; i++)
	{
		printf("%d, ", res[i]);
	}
	printf("%d>", res[n - 1]);
}

코드 (Python)

deque를 사용함

from collections import deque


n, k = map(int, input().split())
queue = deque([i for i in range(1, n+1)])

idx = 0
res = []
while queue:
    idx += 1
    a = queue.popleft()
    if idx % k == 0:
        res.append(a)
    else:
        queue.append(a)

print("<", end = '')
for i in range(n-1):
    print(res[i], end = ', ')
print(str(res[n-1])+'>')