[18258] 큐2

생각

그냥 fp bp 만들어서 해당하는 인덱스거 뽑아내면 된다.
그런데 궁금한 점.
문제에서는 각 연산 당 O(1) 의 시간만 걸려야 한다고 했다.
나는 리스트를 사용해서 큐를 구현할건데, 선택상황은 다음과 같다.
1) fp, bp를 사용하여 fp와 bp의 위치 이동을 통해 큐를 구현한다.
-> 문제점: fp 앞에 있는 원소들은 쓸모없이 공간을 낭비한다.
2) bp만 사용하고, pop을 할때마다 RemoveAt(0) 연산을 실행한다.
-> 문제점: O(n) 시간복잡도가 아닌가?
-> C#에서는 RemoveAt은 O(1) 시간복잡도가 걸린다.
Remove는 탐색까지 합쳐지기 때문에 O(n)이 걸린다.

처음 코드

using System.Text;

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {
            using StreamWriter output = new System.IO.StreamWriter(Console.OpenStandardOutput());

            Queue queue = new Queue();

            int n = int.Parse(Console.ReadLine());

            while (n -- > 0)
            {
                string s = Console.ReadLine();

                if (s.Contains("push"))
                {
                    queue.Push(int.Parse(s.Split()[1]));            
                }
                else
                {
                    switch (s)
                    {
                        case "pop": 
                            output.WriteLine(queue.Pop()); 
                            break;

                        case "size": 
                            output.WriteLine(queue.Size()); 
                            break;

                        case "empty": 
                            output.WriteLine(queue.Empty()); 
                            break;

                        case "front": 
                            output.WriteLine(queue.Front()); 
                            break;

                        case "back": 
                            output.WriteLine(queue.Back()); 
                            break;
                    }
                }
            }
        }
 
    }

    class Queue
    {
        List<int> queue;
        int bp;
        public Queue()
        {
            queue = new();
            bp = 0;
        }

        public void Push(int x)
        {
            queue.Add(x);
            bp++;
        }

        public int Pop()
        {
            if (Empty() == 1)
                return -1;

            int n = queue[0];
            queue.RemoveAt(0);
            bp--;
            return n;
        }

        public int Size()
        {
            return bp;
        }

        public int Empty()
        {
            return bp == 0 ? 1 : 0;
        }

        public int Front()
        {
            return Empty() == 1 ? -1 : queue[0];
        }

        public int Back()
        {
            return Empty() == 1 ? -1 : queue[bp - 1];
        }
    }
}

시간초과남
그래서 앞에서 말했던 다른 방법인 fp를 사용함과 동시에 배열로 변경해주었다.

두번째 코드

using System.Text;

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {
            using StreamWriter output = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(Console.ReadLine());

            Queue queue = new Queue(n);

            while (n -- > 0)
            {
                string s = Console.ReadLine();

                if (s.Contains("push"))
                {
                    queue.Push(int.Parse(s.Split()[1]));            
                }
                else
                {
                    switch (s)
                    {
                        case "pop": 
                            output.WriteLine(queue.Pop()); 
                            break;

                        case "size": 
                            output.WriteLine(queue.Size()); 
                            break;

                        case "empty": 
                            output.WriteLine(queue.Empty()); 
                            break;

                        case "front": 
                            output.WriteLine(queue.Front()); 
                            break;

                        case "back": 
                            output.WriteLine(queue.Back()); 
                            break;
                    }
                }
            }
        }
 
    }

    class Queue
    {
        int[] queue;
        int fp;
        int bp;
        public Queue(int n)
        {
            queue = new int[n];
            fp = 0;
            bp = 0;
        }

        public void Push(int x)
        {
            queue[bp++] = x;
        }

        public int Pop()
        {
            if (Empty() == 1)
                return -1;

            return queue[fp++];
            
        }

        public int Size()
        {
            return bp - fp;
        }

        public int Empty()
        {
            return bp == fp ? 1 : 0;
        }

        public int Front()
        {
            return Empty() == 1 ? -1 : queue[fp];
        }

        public int Back()
        {
            return Empty() == 1 ? -1 : queue[bp - 1];
        }
    }
}

미안해 메모리야!!