백준 1158번 요세푸스 문제: C언어 풀이

백준 1158번 요세푸스 문제 의 C언어 해설입니다.
원형 큐를 이용한 구현 방식과 일반적인 일차원 배열을 이용한 구현 방식을 다루고, 두 방식의 성능 차이를 설명합니다.

큐를 만들어 회전하는 구현

원형 큐를 정의한다. k - 1번 우측으로 회전하고 인간을 POP, 제거 해준다.

사람 수 만큼 회전하면 한 바퀴 돌아서 제자리로 돌아오게 된다.
즉, 회전 수가 사람 수보다 많으면 불필요한 회전을 더 하는 셈이다.
따라서 회전 수를 크기만큼 나눈 나머지를 사용한다.

코드

#include <stdio.h>

#define MAX_SIZE 8192
#define REMAINDER_MASK 8191

int main(void)
{
    int num_people;
    int interval;
    scanf("%d %d", &num_people, &interval);

    // Initialize
    int queue[MAX_SIZE];
    for (int i = 0; i < num_people; i++)
    {
        queue[i] = i + 1;
    }
    int head = 0;
    int tail = num_people;

    int rotation;
    printf("<");
    for (; num_people != 1; num_people--)
    {
        rotation = (interval - 1) % num_people;

        // Rotate
        for (; rotation != 0; rotation--)
        {
            queue[tail] = queue[head];
            head = (head + 1) & REMAINDER_MASK;
            tail = (tail + 1) & REMAINDER_MASK;
        }

        // Pop
        printf("%d, ", queue[head]);
        head = (head + 1) & REMAINDER_MASK;
    }

    // Final person, without comma
    printf("%d>\n", queue[head]);
}

일차원 배열을 이용한 회전하지 않는 구현 방식

제출하고 다른 사람들 코드를 읽다가 발견.

큐를 이용한 회전이 아니라, 일반적인 일차원 배열에서 원소를 삭제해 구현하는 방식이다.
원소를 제거하고 우측에 남아있는 원소를 한 칸씩 앞으로 당기는 데, 이게 훨씬 속도가 빨랐다.

문제 조건 상 새로운 원소를 추가할 필요도 없고,
제거할 때에 부가적인 연산이 적을 뿐더러 특성 상 cache locality가 뛰어나서 더 빠른 걸로 생각된다.

무회전 코드

#include <stdio.h>

#define MAX_SIZE 5000

int main(void)
{
    int num_people, interval;

    scanf("%d %d", &num_people, &interval);

    // Initialize
    int queue[MAX_SIZE];
    for (int i = 0; i < num_people; i++)
    {
        queue[i] = i + 1;
    }

    printf("<");
    int current_index = 0;
    for (; num_people > 1; num_people--)
    {
        current_index = (current_index + interval - 1) % num_people;
        printf("%d, ", queue[current_index]);

        // Kill and rearrange
        for (int i = current_index; i < num_people - 1; i++)
        {
            queue[i] = queue[i + 1];
        }
    }
    // Final person, without comma
    printf("%d>\n", queue[0]);
}