요세푸스 문제

문제

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

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)

출력

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

예제 입력 1

7 3

예제 출력 1

<3, 6, 2, 7, 5, 1, 4>

출처

문제를 만든 사람: author5

알고리즘 분류

• 구현
• 자료 구조
• 큐

해설

요세푸스 문제는 보통 전형적인 환형 큐 문제이다. 그렇지만 코딩 테스트의 시간 제한이 10분 정도일 경우 환형 큐를 다 구현하고 나면 시간이 빠듯하다. 이러한 문제를 짧게 푸는 법을 나의 4년 전 C코드와 방금 10분 안에 작성한 파이썬 코드를 비교하여 해설한다.

C 코드(주석 없음, 가독성 나쁨)

#include <stdio.h>
#include <stdlib.h>
typedef struct _node {int key; struct _node *next;} node;
node *head;
void insert_key(int k)
{
    int i;
    node *t;
    t=(node *)malloc(sizeof(node));
    t->key=1;
    head=t;
    for(i=2;i<=k;i++)
    {
        t->next=(node *)malloc(sizeof(node));
        t=t->next;
        t->key=i;
    }
    t->next=head;
}
void delete_after(node *t)
{
    node *v;
    v=t->next;
    t->next=t->next->next;
    free(v);
}
node* find_key(int k)
{
    node *t;
    t=head;
    while(t->key!=k)
        t=t->next;
    return t;
}
void josephus()
{
    int n,k,i;
    scanf("%d %d", &n, &k);
    insert_key(n);
    putc('<', stdout);
    node *t;
    t=find_key(n);
    while(t!=t->next)
    {
        for(i=0;i<k-1;i++)
            t=t->next;
        printf("%d, ", t->next->key);
        delete_after(t);
    }
    printf("%d>", t->key);
}
int main()
{
    josephus();
}

코드 스타일이 못 봐줄 꼴인 것은 둘째 치고, 이 환형 큐를 다 구현하면 거의 15-20분을 잡아먹을 가능성이 크다. 이런 상황을 타개하기 위해선 배열 기반으로 처리해야 하는데, idx_to_delete = (idx_to_delete + k - 1) % survived_people이라는 공식을 사용해 인덱스의 사람을 배열에서 뽑고 다시 돌리고, 살아 남은 사람 수로 나머지를 구한다. 부동소수점 오류를 피하기 위해 만약 살아 남은 사람 수가 0이면 바로 for문을 빠져나가야 한다. C로는 이거나 저거나 구현 난이도가 비슷하고, 그나마 환형 큐가 쉬울 것이다.

이럴 때는 파이썬을 사용하거나 C++를 사용하면 쉽다. 코딩 테스트 환경이라 루비, 루아 등은 못 쓰고, 시간이 빠듯한 경우를 고려할 것이기 때문에 파이썬을 쓰도록 하겠다.

파이썬 코드

def main():
    n, k = map(int, input().split())

    survived = n
    idx_to_remove = 0
    lst = []
    print("<", end="")
    for i in range(n):
        lst.append(i+1)
    for i in range(n):
        if survived == 0:
            break
        idx_to_remove = (idx_to_remove + k - 1) % survived
        survived-=1
        v = lst[idx_to_remove]
        if i < n - 1:
            print(v, end=", ")
        else:
            print(v, end=">")
        lst.remove(v)

if __name__ == "__main__":
    main()

• 출력은 print의 end 인자로 정리
• 죽은 사람은 리스트에서 제거
• 살아남은 사람 수를 1씩 빼거나 survived 대신 len 사용
• survived가 0으로 떨어지면(혹은 리스트가 비어있으면) 반복문 종료

훨씬 짧은 코드이고 생각하는 시간을 포함해도 10분이면 충분하다.

결론

• 파이썬을 잘 익혀두자
• C로 개인 프로젝트 개발을 해도 파이썬 복습은 중요하다
• 그래도 생각이 안 나면 C++을 쓰자