[C#] 백준 2164번 문제풀이

안녕하세요.
C#을 이용한 백준 2164번 풀이를 해보도록 하겠습니다.

해당 문제는 1~N까지의 수를 받아 첫번째 수를 삭제시키고 두번째 수를 맨 뒤로 보내는 것을 반복시키는 규칙을 가지고 마지막 숫자 하나가 남으면 하나 남은 숫자를 출력하는 문제입니다.

    class aaa
    {
        public static void Main(string[] args)
        {
            List<int> numlist = new List<int>();
            int maxnum = int.Parse(Console.ReadLine());

            for (int i = 1; i <= maxnum; i++)
            {
                numlist.Add(i);
            }

            int n = 0;
            while(numlist.Count() != 1)
            {
                if (n == 0)
                {
                    numlist.RemoveAt(0);
                    n++;
                }
                else if (n == 1)
                {
                    int a = numlist[0];
                    numlist.Add(a);
                    numlist.RemoveAt(0);
                    n--;
                }
            }

            Console.WriteLine(numlist[0]);
        }
    }

 

위 코드를 작성한 후에 백준에 제출을 하였습니다.
그러나 시간초과가 발생하였습니다.

시간을 줄이기 위해 기존 리스트의 시간복잡도가 O(n^2)인것을 고려하여 시간복잡도가 O(n)인 Queue를 사용하여 코드를 다시

작성하였습니다.

정답코드:

    class aaa
    {
        public static void Main(string[] args)
        {
            Queue<int> numlist = new Queue<int>();
            int maxnum = int.Parse(Console.ReadLine());

            for (int i = 1; i <= maxnum; i++)
            {
                numlist.Enqueue(i);
            }
            while(numlist.Count() > 1)
            {
                numlist.Dequeue(); // 맨 앞 제거
                numlist.Enqueue(numlist.Dequeue()); // 맨 앞을 뒤로보냄
            }

            Console.WriteLine(numlist.Peek());
        }
    }

 

코드를 더 효율적으로 작성한 후 시간초과 문제까지 해결하여 백준 2164번 문제를 해결하였습니다.
감사합니다.