[백준/c++] 1021 - 회전하는 큐

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

1021번: 회전하는 큐

---

1) 풀이

문제에서 '위치'라는 말이 문제를 조금 헷갈리게 한다고 생각하는데,

이 위치를 인덱스라고 생각하지 말고,

1~n까지 덱에 삽입하고 이 삽입된 값들을 '위치'라고 생각하고

옮기면 되는 문제이다.

 

즉, 정리해보자면

'뽑고자 하는 수(위치)를 최소 연산(오른쪽/왼쪽으로 옮기기)으로

제일 앞으로 옮기고 pop_front 를 해라'

 

해당 문제에서 고려할 사항과 풀이 순서는 다음과 같다.

• 제일 앞에서만 수를 뽑을 수 있으므로, 덱(deque)을 이용함

* 큐(queue)는 맨뒤에서만 삽입하고 맨앞에서만 삭제할 수 있는 자료구조인 반면에, 덱(deque)은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조임.

• 주어진 수(위치)를 맨 앞으로 옮길시 오른쪽/왼쪽 중 연산이 적게 드는 쪽 어딘지 계산
• 2, 3번 연산(오른쪽/ 왼쪽으로 옮기기)이 얼마나 진행되는지 카운팅
• 카운팅한 수 출력

처음엔 '적게 드는 연산'에만 너무 몰두한 나머지

입력되는 수 하나하나를 직접 오른쪽/왼쪽으로 옮겨보고

(덱에서 해당 수를 오른쪽으로 옮기며 카운팅, sort함수로 다시 정렬하여 왼쪽으로 카운팅)

조건 연산자를 통해 총 카운팅을 저장할 변수에 둘 중 더 작은 수를 더하려고 했다. 

 

두번째 입력받은 수의 상황을 생각해볼 때부터

이 방법이 틀렸다는 걸 깨달았는데😂

두번째 입력받은 수를 맨앞으로 옮기는 상황을 생각해볼때

이전의 수를 옮기고 난 후 덱의 상황에서 진행되기 때문에 

내가 생각한 방법은 카운팅은 쉽게 할 수 있을지 몰라도,

옮겨지고 난 후 덱의 상황을 처리하기 힘들었다.

 

그래서, 나는 어느쪽으로 옮기는 게 더 효율적인지

알아보기 위해 find 함수를 사용하였다.

💡find 함수란?
Iterator find (InputIterator first, InputIterator last, const T& val)
- val의 값이 어디의 위치에 존재하는지를 Iterator로 반환해줌
(val과 일치하는게 없을 시 마지막 end()를 반환)
- #include <algorithm> 을 포함시켜주어야 함
-iterator끼리 빼면 거리가 나오는 점을 이용하여 찾고자 하는 값의 인덱스를 알 수 있음!

(해

즉, find 함수로 입력받은 값이 현재 어느 idex에 위치해있는지 찾으면

해당값을 오른쪽으로 옮겼을 때의 연산의 수, 왼쪽으로 옮겼을 때의 연산을 계산해볼 수 있고,

계산된 결과 중 더 작은 값을 기준으로 연산을 수행하면 된다!

설명으로는 이해가 부족할 것 같으니, 아래의 코드와 주석을 살펴보자.

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
int n, m; //첫번째 줄에 입력할 n과 m
deque<int>d; // 1부터 n까지 들어있는 덱
vector<int>v; //m개의 입력받은 수를 저장할 벡터

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) { //1부터 n까지 삽입
		d.push_back(i);
	}
	while (m--) { //뽑아야 하는 수(위치) 입력
		int t;
		cin >> t;
		v.push_back(t);
	}
	int ans = 0; //총 연산횟수
	for (auto c : v) { 
		int idx = find(d.begin(), d.end(), c)-d.begin(); 
		//찾아야하는 수가 지금 어느 idex에 있는지 계산
		int res = (idx <= (d.size()-idx) ? 0 : 1);
		//idx: 왼쪽 연산 수. d.size()-idx: 오른쪽 연산 수
		if (res == 0) {//왼쪽으로 옮기는 경우
			while (c!=d.front()) {
				d.push_back(d.front());
				d.pop_front();
				ans++;
			}
			d.pop_front(); //해당 수가 front에 도착하여 pop
		}
		else if (res == 1) {//오른쪽으로 옮기는 경우
			while (c != d.front()) {
					d.push_front(d.back());
					d.pop_back();
					ans++;
			}
			d.pop_front(); //해당 수가 front에 도착하여 pop
		}
		
	}
	cout << ans << '\n';
	

}

 

3) 참고자료

ldgeao99.tistory.com/260

torbjorn.tistory.com/265