[백준] 1158 요세푸스(C#)

문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

N크기의 숫자 배열을 생성한 뒤 K번째 수를 제거하면 된다.

 

ex) 7 3

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

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

코드

using System;
using System.Text;
using System.Collections.Generic;

namespace baekjoon
{
    class Algorithm
    {
        static void Main(string[] str)
        {
            string input = Console.ReadLine();
            string[] s = input.Split(' ');
            int n = int.Parse(s[0]); // 7
            int distance = int.Parse(s[1]); // 3
            
            Queue<int> q = new Queue<int>();
            StringBuilder sb = new StringBuilder();
            sb.Append("<");
            
            for(int i = 0; i < n; i++)
            {
                q.Enqueue(i+1);
            }
            
            int cnt = 0;
            while(q.Count > 1)
            {
                cnt++;
                
                if(cnt == distance)
                {
                    int temp = q.Dequeue();
                    sb.Append(string.Format("{0}, ", temp));
                    cnt = 0;
                }
                else
                {
                    int temp = q.Dequeue();
                    q.Enqueue(temp);
                }
            }
            sb.Append(string.Format("{0}>", q.Dequeue()));
            Console.WriteLine(sb);
        }
    }
}

고민

솔직히 어떻게 풀어야할지 몰랐다. 배열로 해야하나? 리스트? 만들고 삭제? 시간이 많이 걸릴 거 같은데? K번째를 삭제해가는 로직은? 그래서 요세푸스를 검색했고 큐로 풀어야 한다는 사실을 알게되었다.

 

Queue에 1번부터 N번까지 숫자를 순서대로 넣은 다음에

K번째 수가 맞으면? Dequeue() 아니면? Dequeue(), Enqueue()

 

손으로 그려보면 편하다.

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

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

3, 4, 5, 6, 7, 1, 2 <= K번째!

 

Dequeue();

<3, 

 

4, 5, 6, 7, 1, 2

5, 6, 7, 1, 2, 4

6, 7, 1, 2, 4, 5 <= K번째!

 

Dequeue();

<3, 6

 

...

 

이런식으로! 하면 된다!