백준알고리즘 1158번 요세푸스 문제 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 1158
• 문제명: 요세푸스 문제
• 언어: 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)

 

출력

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

 

풀이

Queue<int>를 사용하면 int temp = (int) queue.Dequeue();로 표시하지 않아도 된다.

1부터 K - 1번까지의 사람들은 임시 변수에 저장 후 맨 뒤로 이동시킨다.

using System.Text;

// StreamReader, Streamwriter, StringBuilder 선언
StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
StringBuilder sb = new StringBuilder();

// Queue<int> 사용으로 int temp = queue.Dequeue();에서 언박싱이 불필요
// int temp = (int) queue.Dequeue();로 표시하지 않아도 된다.
Queue<int> queue = new Queue<int>();
// 원을 이루며 앉아있을 사람의 수와 제거할 번호 입력
int[] nk = sr.ReadLine().Split().Select(int.Parse).ToArray();

// 1부터 N까지의 번호를 가진 사람들이 원을 이루어 앉는다
for (int i = 1; i <= nk[0]; i++)
    queue.Enqueue(i);

sb.Append("<");

while(queue.Count > 1)
{   
    // 1부터 K - 1까지의 사람들은 자리 뒤로 이동한다.
    for (int i = 1;i < nk[1]; i++)
    {
        // 임시 변수에 저장
        int temp = queue.Dequeue();
        // 큐의 맨 뒤로 이동
        queue.Enqueue(temp);
    }
    // K번째 사람의 번호를 대입
    sb.Append(queue.Peek() + ", ");
    // K번째 값을 제거
    queue.Dequeue();
}
// 마지막 남은 사람의 정보 대입
sb.Append(queue.Peek() + ">");
// 최종 결과 출력
sw.WriteLine(sb.ToString());

sr.Close();
sw.Close();

 

후기

이번에는 Queue가 아니라 Queue<int>를 사용해서 풀어보았는데 using System.Collections;을 사용하지 않아도 될 뿐만 아니라 지난번처럼 temp =  (int) queue.Dequeue();로 처리할 필요 없이 그냥 temp = queue.Dequeue();를 사용해도 된다. 알아가는 재미가 바로 이것인 듯 하다.