1158: 요세푸스 문제

2493번: 탑(BOJ C/C++)

사용 언어: C

 

문제

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

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)

 

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

첫 번째 풀이

이 문제가 큐로 분류되어있어서 일단 첫 번째 풀이는 큐를 적용한 풀이로 풀자고 생각해서 원형 큐로 구현해서 풀었다. 원래 구현한 원형 큐와는 enqueue와 dequeue를 문제에 맞게 조금 다르게 바꿨지만 풀이의 맥락을 읽어보면 이해가 될 거라고 생각한다. 근데 이 방식으로 풀어보니 답을 제출했을 때 실행 시간이 많이 크게 나와서 이게 정공법은 아니구나.. 생각하게 돼서 두 번째 풀이도 작성하게 되었다.

#include <stdio.h>

int front;
int rear;

void init_queue()
{
    rear = 0;
    front = 0;
}

void enqueue(int data, int size, int* queue)
{
    queue[rear]=data;
    rear = (rear+1)%size;
}

int dequeue(int size, int* queue)
{
    int tmp = queue[front];
    front = (front+1)%size;
    return tmp;
}

int main()
{
    int N,K, tmp, k=1;
    scanf("%d %d",&N,&K);
    int queue[N];
    int requeue[N];
    for(int i=1;i<=N;i++)
        enqueue(i, N, queue);

    front=K-1;
    requeue[0]=queue[front];
    printf("<"); printf("%d",requeue[0]);
    queue[front]=0;
    for(int i=0;i<N-1;i++)
    {
        int num=K;
        while(num--)
        {
            while(queue[front]==0) //0이 아닌 값 찾기
            front = (front+1)%N;
            tmp=dequeue(N, queue);
        }
        requeue[k]=tmp;
        k++;
        if(front-1>=0)
            queue[front-1]=0;
        else //front-1<0
            queue[N-1]=0;
    }
    for(int i=1;i<N;i++)
        printf(", %d",requeue[i]);

    printf(">\n");
    return 0;
}

두 번째 풀이

간단히 배열로 뽑은 부분은 덮어 씌우면서 배열 검사할 부분은 줄이면서 풀 수 있다.

#include <stdio.h>

int main(){
    int N, K, j=0;
    int arr[5000];

    scanf("%d",&N);
    scanf("%d",&K);

    for(int i=0; i<N; i++)
        arr[i]=i+1;

    printf("<");

    do{
        j=(j+K-1)%N;
        printf("%d",arr[j]);
        for(int i=j; i<N-1; i++)
            arr[i]=arr[i+1]; //뽑은 숫자 덮어 씌우기
        if(N==1)
        {
            printf(">\n");
            break;
        }
        else
            printf(", ");
    }while(N--); //N--로 배열 검사할 부분 감소
    return 0;
}

 

느낀 점

굳이 큐로 먼저 푸는 것은 그저 자료구조를 연습하려고 하는 것 뿐이다. 언젠가 자료구조를 능히 잘한다고 스스로 생각하게 되면, 각 문제마다 실행시간이 가장 빠르고 실행공간이 가장 적을 방법으로 풀 생각이다. 물론 그렇다고 아예 자료구조 식으로만 구현한다는 것은 아니다. 이번 문제처럼 말이다.