문제

지민이는 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

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N, M, num, cnt = 0;
	vector<int> deque;

	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++)
		deque.push_back(i);

	while (M--) {
		scanf("%d", &num);

		int front = 0, back = 0;
		// 앞 & 뒤에서 가장 가까운쪽 찾기
		for (int i = 0; i < N ; i++) {
			if (deque[i] == num) {
				front = 1;
				break;
			}
			else if (deque[N - 1 - i] == num) {
				back = 1;
				break;
			}
		}

		// 더 가까운쪽에서부터 시작
		if (front) {
			while (1) {
				int front_num = deque.front();
				deque.erase(deque.begin());

				if (front_num == num)
					break;
				deque.push_back(front_num);
				cnt++;
			}
		}
		else {
			cnt++;
			while (1) {
				int back_num = deque.back();
				deque.pop_back();

				if (back_num == num)
					break;
				deque.insert(deque.begin(), back_num);
				cnt++;
			}
		}

		N--;
	}

	printf("%d\n", cnt);

	return 0;
}

풀이1

문제의 난이도에 비해 정답률이 낮은것 같다.
약간 헷갈렸던 부분이 두번째 줄에 뽑아야할 숫자를 나열하는데, 이를 순서대로 뽑는지 아니면 마구잡이로 먼저 발견하면 뽑는 것인지였다.
나열한 순서대로 숫자를 뽑으면 되는 것이었다.

처음 문제에 접근할때는 가장 단순한 방법이 떠올랐다.
앞과 뒤에서부터 쭉 조사해서 가장 가까운 쪽부터 시작하는 방식이다.
가장 가까운 곳부터 시작한다면 연산의 최솟값이 나오기 때문이다.
따라서 위의 구현 코드를 보면 Deque의 front, back에서 가장 가까운 쪽을 선택해서 count 해주는 방식으로 되어있다.

1.가까운쪽을 찾기위해 탐색

1. 해당 숫자를 지우고 deque의 나열을 바꾸기 위해 탐색

굳이 2번이나 탐색을 하기 때문에 비효율적으로 느껴져서 이를 줄여보기로 했다.

코드2

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int N, M, num, cnt = 0;
	vector<int> deque;

	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++)
		deque.push_back(i);

	for (int j = 0; j < M; j++) {
		scanf("%d", &num);

		for (int i = 0; i < N; i++) 
			if (deque[i] == num) {

                // 앞&뒤에서 탐색한 것 중에서 빠른 쪽을 cnt더해줌
				cnt += min(i, N - i);
                
                // 해당 범위를 rotate해줌. (알맞게 deque원소 정렬)
				rotate(deque.begin(), deque.begin() + i + 1, deque.end() - j);
				break;
			}

		N--; // 원소하나를 뽑아냈기 때문에 Deque의 원소 갯수가 줄어듬
	}

	printf("%d\n", cnt);

	return 0;
}

풀이2

코드1에 비해 확연히 간결해졌다.
코드1에서 두번이나 탐색했던 이유는 deque의 원소나열을 바꿔야했기 때문이다.
구글링을 하던중 새로운 함수를 알게되었는데, algorithm 헤더에 속해있는 rotate() 라는 함수이다.
rotate() 함수는 지정한 구간의 원소들의 순서를 바꿔버리는 함수다.

rotate(swap_start, swap_end, end) : swap_start ~ swap_end 구간에 해당하는 원소들을 end 위치에 보내버림.

이 함수를 사용하므로 인해 탐색 1번으로 최소값과 deque정렬까지 가능해졌다.