[ BOJ ] 1158 : 요세푸스 문제 ( SILVER 4 ) / C, Python

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

풀이 과정

큐를 이용해 해당 문제 상황을 해결할 수 있다.

N이 7이라고 가정하면, 시계 방향으로 사람들은 1, 2, 3, 4, 5, 6, 7 로 앉아있다.

이제, 3번째 사람을 계속해서 제거한다.

큐 자료구조는 맨 앞에 있는 요소를 제거할 수 있으므로, 3번째 사람이 아닌 1번째 사람, 2번째 사람은 스킵한단 느낌으로 맨 앞에서 빼서 다시 맨 뒤로 넣는다.

3번째 사람을 빼고, 다시 1번째 사람부터 카운트해서 큐에 사람이 아무도 남지 않을 때 까지 원을 도는 것처럼 탐색한다.

 

Queue : [ 1, 2, 3, 4, 5, 6, 7 ] 현재 큐 맨 앞에는 1번째 사람

Queue : [ 2, 3, 4, 5, 6, 7, 1 ] 현재 큐 맨 앞에는 2번째 사람

Queue : [ 3, 4, 5, 6, 7, 1, 2 ] 현재 큐 맨 앞에는 3번째 사람 -> (3)

Queue : [ 4, 5, 6, 7, 1, 2 ] 현재 큐 맨 앞에는 1번째 사람

Queue : [ 5, 6, 7, 1, 2, 4 ] 현재 큐 맨 앞에는 2번째 사람

Queue : [ 6, 7, 1, 2, 4, 5 ] 현재 큐 맨 앞에는 3번째 사람 -> (6)

Queue : [ 7, 1, 2, 4, 5 ] 현재 큐 맨 앞에는 1번째 사람

Queue : [ 1, 2, 4, 5, 7 ] 현재 큐 맨 앞에는 2번째 사람

Queue : [ 2, 4, 5, 7, 1 ] 현재 큐 맨 앞에는 3번째 사람 -> (2)

Queue : [ 4, 5, 7, 1 ] 현재 큐 맨 앞에는 1번째 사람

Queue : [ 5, 7, 1, 4 ] 현재 큐 맨 앞에는 2번째 사람

Queue : [ 7, 1, 4, 5 ] 현재 큐 맨 앞에는 3번째 사람 -> (7)

Queue : [ 1, 4, 5 ] 현재 큐 맨 앞에는 1번째 사람

Queue : [ 4, 5, 1 ] 현재 큐 맨 앞에는 2번째 사람

Queue : [ 5, 1, 4 ] 현재 큐 맨 앞에는 3번째 사람 -> (5)

Queue : [ 1, 4 ] 현재 큐 맨 앞에는 1번째 사람

Queue : [ 4, 1 ] 현재 큐 맨 앞에는 2번째 사람

Queue : [ 1, 4 ] 현재 큐 맨 앞에는 3번째 사람 -> (1)

Queue : [ 4 ] 현재 큐 맨 앞에는 1번째 사람

Queue : [ 4 ] 현재 큐 맨 앞에는 2번째 사람

Queue : [ 4 ] 현재 큐 맨 앞에는 3번째 사람 -> (4)

Queue : [ ]

 

만약 N이 5000이고 K가 5000인 경우에, Queue에 사람이 적게 남아있을 때 5000번째 사람을 탐색하려고 4999번 스킵을 여러 번 진행할 수도 있다. 이러한 스킵 과정을 나머지 연산으로 축소시킬 수 있다.

Queue 에 남아 있는 사람 길이보다 K가 더 크다면, K % 큐 사이즈 + ((K % 큐 사이즈 == 0) ? 큐 사이즈 : 0) 번째 사람이 K 번째 사람이다.

C

#include <stdio.h>
 
int queue[25000000];
int rear = -1;
int top = -1;
 
int size() { return top - rear; }
int empty() { return (size()) ? 0 : 1; }
int front() { return (empty()) ? -1 : (queue[rear + 1]); }
int back() { return (empty()) ? -1 : (queue[top]); }
void push(int x) { queue[++top] = x; }
int pop() { 
    if (empty()) return -1;
    else return queue[++rear]; 
}
void skip() {
    int x = pop();
    push(x);
}
 
int main(void) {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) push(i);

    printf("<");
    while (!empty()) {
        if (size() != n) printf(", ");

        int skip_count = k % size() + (((k % size()) == 0) ? size() : 0);
        for (int i = 0; i < skip_count - 1; i++) skip();
        printf("%d", front());
        rear++;
    }
    printf(">");
    return 0;
}

Python

from collections import deque
import sys
input = sys.stdin.readline

n, k = map(int, input().rstrip().split())
queue = deque()
for i in range(1, n+1): queue.append(i)

def skip():
    queue.append(queue.popleft())

result = []
while queue:
    skip_count = k % len(queue) + (len(queue) if k % len(queue) == 0 else 0)
    for _ in range(skip_count - 1): skip()
    result.append(queue.popleft())

print('<' + ', '.join(map(str, result)) + '>')