[baekJoon1021] 회전하는 큐(STL/deque정리)

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

1021번: 회전하는 큐

---

[STL] deque container 정리

▷ 헤더파일: <deque>

▷ 생성자

deque dq;	빈 컨테이너 dq 생성
deque dq(n);	기본값으로 초기화된 n개의 원소 갖는 dq 생성
deque dq(n, x);	x의 값으로 초기화된 n개의 원소 갖는 dq 생성
deque dq(dq2);	dq2를 복사한 dq 생성

▷ 멤버 함수

dq.assign(2, 5);	값을 2로 갖는 원소 5개 할당
dq.front();	첫 번째 원소 참조
dq.back();	마지막 원소 참조
dq.clear();	모든 원소 제거
dq.push_front(8);	첫 번째 원소 앞에 원소 8을 삽입
dq.pop_front();	첫 번째 원소 제거
dq.push_back(5);	마지막 원소 뒤에 원소 5를 삽입
dq.pop_back();	마지막 원소 제거
dq.begin(); / dq.end();	iterator와 사용
dq.rbegin(); / dq.rend();	(역) iterator와 사용
dq.resize(n);	크기를 n으로 변경 (비어있는 원소는 0으로 초기화)
dq.resize(n,3);	크기를 n으로 변경 (비어있는 원소는 3으로 초기화)
dq.size();	원소의 개수를 반환
dq2.swap(dq1);	dq1과 dq2를 바꿈
dq.insert(1, 2, 3);	1번째 위치에 2개의 3을 삽입
dq.insert(3, 4);	3번째 위치에 원소 4 삽입, 삽입한 곳의 iterator를 반환
dq.erase(iter);	iterator가 가리키는 원소 제거, 더 적은 쪽 원소 당겨 채움
dq.empty();	dq가 비었다면 true를 반환

▷ 특징: 메모리 재할당 후 원소를 복사하는 방식으로 성능 저하가 되었던 vector의 단점을 보완

---

/*
날짜: 2020.08.07
번호: 1021
문제: 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
*/
#include <iostream>
#include <deque>
using namespace std;
int main() {
	int N;	cin >> N; // 크기
	int M; cin >> M; // 뽑아낼 원소 개수
	
	deque<int> dq;
	for (int i = 1; i <= N; ++i) {
		dq.push_back(i);
	}

	int idx = 0;
	int cnt = 0; // 이동 횟수

	while (M--) {
		int get;	cin >> get; // 뽑아낼 원소
		int size = dq.size();

		/* 원소 위치 파악 */
		for (int i = 0; i < size; ++i) {
			if (dq[i] == get) {
				idx = i;	break;
			}
		}

		// 2번 연산 시 idx번 수행
		// 3번 연산 시 dq.size()-idx번 수행
		
		/* 2번 연산을 택하는게 최소인 경우 */
		if (idx < (size - idx)) {
			while (1) {
				if (dq.front() == get) {
					dq.pop_front();	break;
				}
				else {
					cnt++;
					dq.push_back(dq.front());
					dq.pop_front();
				}
			}			
		}

		/* 3번 연산을 택하는게 최소인 경우 */
		else {
			while (1) {
				if (dq.front() == get) {
					dq.pop_front();	break;
				}
				else {
					cnt++;
					dq.push_front(dq.back());
					dq.pop_back();
				}
			}
		}
	}
	
	cout << cnt << "\n";
}