백준 C# - 1021 +) 풀이

이 문제는 Deque(덱) 자료구조를 사용해서 풀어야 되는 문제이다.

C#은 제공되는 Deque(덱)자료구조가 없어서  직접 Queue를 이용해서 풀어야한다.

 

Deque의 특징

큐와는 달리 항목의 추가와 삭제가 머리와 꼬리 양쪽 끝 모두에서 처리가 가능하다.

(문제에서 자세히 안내되어있다)

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

과정 그림으로 예시

10 3
2 9 5

알고리즘

01 목표 원소의 인덱스를 찾기

int index = deque.IndexOf(targets[0]);

02 목표 원소의 인덱스가 리스트의 크기의 절반 이하인 경우에 왼쪽으로 회전

if (index <= deque.Count / 2) 
{
    for (int j = 0; j < index; j++) 
    {
        int temp = deque[0]; 
        deque.RemoveAt(0); // 맨 앞 요소 삭제
        deque.Add(temp);  // 맨 끝에 추가
        count++; 
    }
}

03 목표 원소의 인덱스가 리스트의 크기의 절반 이인 경우에 오른쪽으로 회전

else
{
    for (int j = 0; j < deque.Count - index; j++) 
    {
        int temp = deque[deque.Count - 1];
        deque.RemoveAt(deque.Count - 1); // 맨 끝 삭제
        deque.Insert(0, temp);  // 맨 앞에 추가
        count++; 
    }
}

04 리스트에서 첫번째 원소 및 타켓 원소 제거

deque.RemoveAt(0);
targets.RemoveAt(0);

---

코드 전문

using System;
using System.Collections.Generic;

namespace baek2
{
    class Program
    {
        public static void Main()
        {
            int count = 0;
            List<int> deque = new List<int>();
            string[] input = Console.ReadLine().Split();           
            int n = int.Parse(input[0]);
            int m = int.Parse(input[1]);
            for (int i = 1; i <= n; ++i)
                deque.Add(i);

            string[] input2 = Console.ReadLine().Split();
            List<int> targets = new List<int>();
            for (int i = 0; i < input2.Length; i++)
                targets.Add(int.Parse(input2[i]));

            for (int i = 0; i < m; i++)
            {
                int index = deque.IndexOf(targets[0]);
                if (index <= deque.Count / 2) 
                {
                    for (int j = 0; j < index; j++) 
                    {
                        int temp = dequeue[0];
                        deque.RemoveAt(0); 
                        deque.Add(temp); 
                        count++; 
                    }
                }
                else
                {
                    for (int j = 0; j < deque.Count - index; j++) 
                    {
                        int temp = deque[deque.Count - 1];
                        deque.RemoveAt(deque.Count - 1); 
                        deque.Insert(0, temp); 
                        count++; 
                    }
                }
                deque.RemoveAt(0);
                targets.RemoveAt(0);
            }
            Console.Write(count);
        }
    }
}