[코딩테스트] BOJ 1021 - 회전하는 큐 (실패)

 

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

1021번: 회전하는 큐

 

 

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

 

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

 

예제 입력1

10 3
1 2 3

 

예제 출력1

0

 

 

예제 입력2

10 3
2 9 5

 

예제 출력2

8

 

 

예제 입력3

32 6
27 16 30 11 6 23

 

예제 출력3

59

 

 

예제 입력4

10 10
1 6 3 2 7 9 8 4 10 5

 

예제 출력4

14

 

 

풀이

문제를 이해하는데만 시간을 많이 썼다. 

N개의 원소를 포함하고 있는 양방향 큐가 있다고 했는데, 이 큐에 어떤 원소가 N개 저장되어 있는지 문제에서 주어지지 않았다. 

그래서 한동안 큐에 들어가 있는 원소가 뭔지도 모르는데 문제를 어떻게 풀지 생각만 하고 있었다. 

 

사실 큐에 뭐가 들어가든 상관이 없었다. 이 문제에서는 두번째 입력으로 뽑아내려고 하는 수의 위치가 주어진다. 

큐에서 1번째, 2번째, 3번째, ... , n번째 숫자를 뽑는데 2번 3번 연산이 최소 몇번 드는가를 묻는 문제이지 큐에 어떤 숫자가 들어가 있든 상관이 없다. 

 

그래서 난 큐에 1~N을 넣고 문제를 풀어봤다.

 

 

코드 - 오답 

namespace 덱
{
    internal class BOJ1021_회전하는큐
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        static int[] deque;
        static int head;
        static int tail;

        public static void Push_Front(int x)
        {
            deque[--head] = x;
        }

        public static void Push_Back(int x)
        {
            deque[tail++] = x;
        }

        public static void Pop_Front()
        {
            head++;
        }

        public static void Pop_Back()
        {
            tail--;
        }

        public static int Front()
        {
            return deque[head];
        }

        public static int Back()
        {
            return deque[tail - 1];
        }

        static void Main(string[] args)
        {
            string[] input;

            input = sr.ReadLine().Split(" ");
            int N = int.Parse(input[0]); // 큐 크기 
            int M = int.Parse(input[1]); // 뽑아내려는 원소의 개수

            deque = new int[2 * N + 1];
            head = N;
            tail = N;

            // 덱에 1~N까지 넣기
            for(int i = 1; i < N+1; i++)
            {
                Push_Back(i);
            }

            input = sr.ReadLine().Split(" ");
            int[] array = new int[input.Length]; // 뽑아내려는 수의 위치 배열 
            for(int i = 0; i < input.Length; i++)
            {
                array[i] = int.Parse(input[i]);
            }

            int answer = 0;
            int target = 0; 
            for(int i = 0; i < array.Length; i++)
            {
                target = array[i];

                // target(=array[i])이 덱에 있나? 
                if(target < N / 2)
                {
                    // head에서 찾기 
                    while (true)
                    {
                        if (Front() == target)
                        {
                            // 1번 방식 수행
                            Pop_Front();
                            break;
                        }
                        else
                        {
                            // 2번 방식 수행
                            Pop_Front();
                            Push_Back(deque[head - 1]);
                            answer++;
                        }
                    }
                }
                else
                {
                    // tail에서 찾기 
                    while (true)
                    {
                        if(Back() == target)
                        {
                            Pop_Back();
                            break;
                        }
                        else
                        {
                            Pop_Back();
                            Push_Front(deque[tail]);
                            answer++;
                        }
                    }
                }
            }

            sw.WriteLine(answer);

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

 

IndexOutOfRangeException 에러가 난다. 

그리고 이 문제에서 원소를 뽑는 연산은 Pop_Front이다. 

그런데 내 코드는 원소를 뽑는 연산으로 Pop_Front, Pop_Back을 하고 있다. 따라서 이 코드는 오답이다. 

 

 

코드2 - 정답

namespace 덱
{
    internal class BOJ1021_회전하는큐
    {
        public const int MX = 1000005;
        public static readonly int[] dat = new int[2 * MX + 1];
        public static int head = MX;
        public static int tail = MX;

        public static void push_front(int x)
        {
            dat[--head] = x;
        }

        public static void push_back(int x)
        {
            dat[tail++] = x;
        }

        public static void pop_front()
        {
            head++;
        }

        public static void pop_back()
        {
            tail--;
        }

        public static int front()
        {
            return dat[head];
        }

        public static int back()
        {
            return dat[tail - 1];
        }

        public static int find_idx(int target)
        {
            for(int i = head; i < tail; i++)
            {
                if (dat[i] == target)
                    return i - head;
            }

            return -1;
        }

        public static int size()
        {
            return tail - head;
        }

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int n = 0;
            int m = 0;

            string[] input;
            input = sr.ReadLine().Split(" ");
            n = int.Parse(input[0]);
            m = int.Parse(input[1]);

            input = sr.ReadLine().Split(" ");
            int[] targets = new int[input.Length];
            for(int i = 0; i < targets.Length; i++)
            {
                targets[i] = int.Parse(input[i]);
            }

            for(int i = 1; i < n+1; i++)
            {
                push_back(i);
            }

            int answer = 0;

            for(int i = 0; i < m; i++)
            {
                int target = targets[i];
                int index = find_idx(target);
                int currentSize = size();

                while (front() != target)
                {
                    if(index < (double)currentSize / 2)
                    {
                        push_back(front());
                        pop_front();
                    }
                    else
                    {
                        push_front(back());
                        pop_back();
                    }
                    answer++;
                }
                pop_front();
            }

            sw.WriteLine(answer);

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

 

원소를 뽑는 연산은 Pop_Front로 해줬고, 인덱스 문제도 해결했다.