큐,덱 - 백준 1021번 회전하는 큐

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

IDEA

문제에서 양방향 순환 큐라는 얘기를 한다 -> 양방향 큐 = 덱 이라고 생각하고 문제를 풀었다. 

 

아래와 같은 3가지 조건을 수행한 후 2,3번을 수행하는데 얼마나 걸렸는지 구하는 문제다. 

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
   👉 내가 맨 처음에 착각했던 문구다. 원소를 뽑아내는 행위는 맨 앞에서만 할 수 있다. 
         pop_front()를 이용하면 된다. 
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
   👉 앞에 있던 원소가 뒤로 이동한다. front를 저장해놓고 pop_front & push_back 콤보 적용
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
   👉 뒤에 있던 원소가 앞으로 이동한다. back을 저장해놓고 pop_back & push_front콤보 적용

여기까지는 큰 무리 없었는데 가장 큰 난관은 앞으로 뽑는게 유리한지, 뒤로 뽑는 게 유리한지 어떻게 알지?였다. 

고민을 해도 모르겠어서 알아봤는데, 내가 잘 알고있는 거라 더 짜증났다.;ㅜ

• iterator를 이용하여 우리가 찾고자하는 타겟의 현재 위치를 알아낸다.
  현재위치 - 0과 덱의 사이즈 - 현재위치 중 더 작은 것을 찾는다.
  예를들어 덱의 사이즈가 7일때, 현재위치가 3이라면 3-0 < 7-3
  전자가 더 작다면 2번을 수행하고 후자가 더 작다면 3번을 수행하면 된다. 

이후 1번을 다시 생각해보면 2번을 할 때는 큰 문제가 없다 front를 확인하고 target이랑 같으면 끝내버리면 된다.

근데 3번은 back이 우리가 찾는 값과 같아도 우리는 front에서 뽑아내야하기때문에 break를 걸어버리면 안된다.

push_front까지 해준 후 front가 target과 같은 지 확인해주어야한다. 

 

CODE

#include <iostream>
#include <deque>
#include <string>
using namespace std;

deque<int> dq;

int main() {
	int n, m, cnt = 0;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) dq.push_back(i);
	for (int i = 0; i < m; i++) {
		int target;
		scanf("%d", &target);

		//target이 있는 위치 알아내기
		int idx = 0;
		for (const auto& i : dq) {
			if (target == i) break;
			else idx++;
		}
		// 거리 비교를 통해 앞으로 뺄 지 뒤로 뺄 지 고르기 
		if (idx - 0 < dq.size() - idx) {
			while (1) {
				int front = dq.front();
				if (front == target) {
					dq.pop_front();
					break;
				}
				else {
					cnt++;
					dq.pop_front();
					dq.push_back(front);
				}
			}
		}
		else {
			while (1) {
				int back = dq.back();
				dq.pop_back();
				cnt++;
				dq.push_front(back);
				if (dq.front() == target) {
					dq.pop_front();
					break;
				}
			}
		}
	}
	printf("%d", cnt);
}