[Silver4] No.01021 회전하는 큐
12 Apr 2022회전하는 큐
문제
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
- 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, …, ak이었던 것이 a2, …, ak와 같이 된다.
- 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, …, ak가 a2, …, ak, a1이 된다.
- 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, …, ak가 ak, a1, …, ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
풀이
해당 문제는 자료구조중에 덱(Deque)을 이용해서 푸는 문제이다.
덱을 간단하게 설명하자면, FIFO(First In First Out) 구조인 Queue와 FILO(First In Last Out) 구조인 Stack을 합친 자료구조로 양방향으로 데이터를 넣고 뺄 수 있는 자료구조를 말한다.
그림으로 설명하자면 이렇다.
자세한 설명이나 구현은 다음기회에 이어가도록 하자.
계속해서 문제를 풀어가보자.
덱의 가장 처음 숫자를 꺼내 첫번째 숫자와 비교한다. 만약 숫자가 동일할시 break를 이용해 반복문을 나가 새로운 숫자를 비교한다. 하지만 숫자가 다를시 덱을 왼쪽으로 이동할지, 오른쪽으로 이동할지 정해주어야 하는데.
연산의 최솟값이므로 왼쪽과 오른쪽 중 최단거리를 택해서 가야한다.
몇가지 예시를 들어보자.
위의 9개의 숫자로 이루어진 배열이 있다.
1에서 7로 이동하고자 할 때, 오른쪽으로 이동시에는 6의 비용이 왼쪽으로 이동 할시에는 3의 비용이 소모된다. 1에서 9로 이동하고자 할 때, 오른쪽으로 이동시에는 8의 비용이 왼쪽으로 이동 할시에는 1의 비용이 소모된다. 1에서 2으로 이동하고자 할때, 오른쪽으로 이동시에는 1의 비용이 왼쪽으로 이동할시에는 8의 비용이 발생한다. 1에서 4으로 이동하고자 할때, 오른쪽으로 이동시에는 3의 비용이 왼쪽으로 이동할시에는 6의 비용이 발생한다.
여기서 규칙을 찾아보자면, 해당 배열의 가운데 인덱스를 기준으로 찾고자 하는 수의 인덱스가 가운데 인덱스보다 작다면 오른쪽, 크다면 왼쪽으로 이동하여 숫자를 찾아 주면 된다.
여기서 주의할 점이있다면, 배열의 갯수가 홀수일 경우인데, 찾고자 하는수의 인덱스와 가운데의 인덱스의 숫자가 같을 수 있다. 이경우에는 시작점은 무조건 0번째 인덱스에서 시작하니 오른쪽으로 이동하는것이 더 적은 비용을 발생한다.
아래의 사진과 같이 말이다.
