요세푸스 문제 (Josephus problem)

• n명의 사람이 원형으로 앉아 있고, k번째 사람마다 제거해 나갈 때, 마지막에 남는 사람을 구하는 알고리즘 문제이다.

---

목표

• 사용자로부터 사람 수(n)와 카운트 수(k)를 입력받아,

• 1번부터 시작하여 k번째 사람을 반복적으로 제거한 뒤,

• 마지막으로 남는 사람의 번호를 출력한다.

---

전체 코드

int people, count;

do
{
    Console.Write("사람 수를 입력해주세요 : ");
}
while (!int.TryParse(Console.ReadLine(), out people));

do
{
    Console.Write("카운트를 입력해주세요 : ");
}
while (!int.TryParse(Console.ReadLine(), out count));

List<int> list = new(people);

for (int i = 1; i <= people; i++)
{
    list.Add(i);
}

int index = 0;
while (list.Count > 1)
{
    for (int i = 1; i < count; i++)
    {
        index++;
        if (index >= list.Count)
        {
            index = (index - list.Count) < 0 ? 0 : index -= list.Count;
        }
    }
    list.RemoveAt(index);
}
Console.WriteLine($"마지막 사람의 번호 : {list[0]}");

---

코드 흐름

int people, count;

do
{
    Console.Write("사람 수를 입력해주세요 : ");
}
while (!int.TryParse(Console.ReadLine(), out people));

do
{
    Console.Write("카운트를 입력해주세요 : ");
}
while (!int.TryParse(Console.ReadLine(), out count));

1. 사용자 입력 받기 (사람 수, 카운트 수)

---

List<int> list = new(people);

for (int i = 1; i <= people; i++)
{
    list.Add(i);
}

2. 1 ~ n 의 번호를 가진 사람 리스트 생성

---

int index = 0;
while (list.Count > 1)
{
    for (int i = 1; i < count; i++)
    {
        index++;
        if (index >= list.Count)
        {
            index = (index - list.Count) < 0 ? 0 : index -= list.Count;
        }
    }
    list.RemoveAt(index);
}
Console.WriteLine($"마지막 사람의 번호 : {list[0]}");

• 3. 리스트의 크기가 1이 될 때까지 반복

• 3-1. for문으로 1부터 count만큼 반복하면서 index를 증가

• 3-2. 증가한 index가 리스트 범위를 벗어나면,
  index -= list.Count를 통해 다시 앞으로 반복되도록 조절

• 4. 반복문이 끝나면 마지막 값 출력

---

Queue로 구현

public static int Josephus(int n, int k)
{
    Queue<int> que = new Queue<int>(n);
    for (int i = 1; i<=n; i++)
    {
        que.Enqueue(i);
    }

    int count = 0;
    while (que.Count > 1)
    {
        count++;

        if (count % k == 0)
        {
            que.Dequeue();
        }
        else
        {
            int value = que.Dequeue();
            que.Enqueue(value);
        }
    }

    return que.Dequeue();
}

• count 가 계속 증가하면서 if (count % k == 0) 일 때만 제거

• else 일 때는 제거하고 다시 추가하여 순환되게 한다.

---

Queue를 사용하니 코드 길이가 확 줄었다.

이처럼 상황에 따라 사용할 줄 알아야 할텐데

여전히 List가 너무 편해서 의존하게된다. ㅠㅠ

---

이미지 출처