[백준 1021번] 회전하는 큐

문제 발췌

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

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

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

문제 원본 보기

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

 

전체 코드

#include <iostream>
#include <queue>
#include <deque>

using namespace std;
int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);

	deque<int> DQ;
	int n, m;
	cin >> n >> m;

	int find;
	int cnt = 0;

	for (int i = 1; i <= n; i++) {
		DQ.push_back(i); // 1부터 n까지 넣기
	}
	// 탐색하는 코드 추가해주기!
	for(int i=0; i<m; i++){ // 찾기 시작
		cin >> find; // 이 기법 알아두기!

		//탐색하는 코드
		int findIdx = 0;
		for (int i = 0; i < DQ.size(); i++) {
			if (DQ[i] == find) {
				findIdx = i;
				break;
			}
		}

		if (findIdx > DQ.size() - findIdx) { // 좀 뒤쪽 그러니까 우측에 있다면
			while (1) {
				if (DQ.front() == find) { // 찾았으면
					DQ.pop_front();
					break;
				}
				DQ.push_front(DQ.back());
				DQ.pop_back();
				cnt++;
			}
		}
		else {
			while (1) {
				if (DQ.front() == find) {
					DQ.pop_front();
					break;
				}
				DQ.push_back(DQ.front());
				DQ.pop_front();
				cnt++;
			}
		}
	}

	cout << cnt;
	return 0;
}

// 내가 몰랐던 것
// 탐색
// DQ.size()를 이용해서 왼쪽에 더 가까운 인덱스인지 오른쪽에 더 가까운 인덱스인지 판별해서
// 2번을 할 지, 3번을 할 지 판별해주는 거!

// 사고에 도달하는 방법은?

코드를 짤 줄 몰랐던 부분

탐색 코드

 

내가 사고 과정에 도달하지 못한 거

인덱스 탐색을 기반으로 이 인덱스가 Deque의 사이즈를 기준으로 왼쪽에 가까운지 우측에 가까운지 판별하는 거

왼쪽에 가깝다면 2번 연산

오른쪽에 가깝다면 3번 연산

(처음에는 나누기 2해서 판별할까 했는데 그거는 명확하지 않아 보여서...ㅠㅠ)

 

사고에 도달하는 방법

1. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
2. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

어떨 때 2번 연산을 쓰면 좋고 어떨 때 3번 연산을 쓰면 좋은지 생각해보기

2번 연산은 숫자가 앞쪽에 있을 때

3번 연산은 숫자가 뒤쪽에 있을 때 하면 좋다.

 

참고 블로그 출처) https://gdlovehush.tistory.com/410

회전하는 큐 백준 1021번 c++