백준 1021

난이도 : 중상

해결 방법 : 풀이 참고(https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x07/solutions/1021.cpp)

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

int N, M;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	deque<int> DQ;
	// 원소의 위치
	for (int i = 1; i <= N; i++) DQ.push_back(i); 
		
	int min = 0;
	while (M--) {
		int position;
		cin >> position;
						
		while (DQ.front() != position) {
			// front에 뽑아내려고 하는 원소의 위치가 없는 경우
			// 2번과 3번에서 어떤 연산을 수행하는게 더 최솟값을 구할수 있는지 체크
			deque<int>::iterator idxPointer = find(DQ.begin(), DQ.end(), position); // position이 위치하는 반복자(주소)를 찾음
			int idx = idxPointer - DQ.begin(); // ex) 2번 원소가 위치하고 있는 주소의 값 - 시작 원소 주소의 값 = 인덱스

			// 2번:왼쪽으로 한 칸 이동
			if (idx < DQ.size() - idx) {
				DQ.push_back(DQ.front());
				DQ.pop_front();
			}
			else {
				// 3번:오른쪽으로 한 칸 이동
				DQ.push_front(DQ.back());
				DQ.pop_back();
			}
			min++;
		}
		DQ.pop_front(); // 1번 연산 수행(front에 위치한 원소를 뽑아냄)
	}

	cout << min;
	
	return 0;
}

 

주어진 원소의 위치를 뽑는데 2번(원소를 왼쪽으로 이동)과 3번 연산(원소를 오른쪽으로 이동)의 최소 횟수가 총 얼만큼 나오는지 계산

ex) 배열의 크기는 5이고, 주어진 원소의 위치가 3, 1 순으로 주어진 경우

첫번째는 3이 위치하는 원소을 뽑기 

-> 3이 front가 되기 위해 2번 연산을 2번 수행

 

두번째는 1이 위치하는 원소를 뽑기

-> 1이 front에 오기 위해서 2번 연산을 2번 수행(3번 연산을 2번 수행해도 동일)

 

 

front에 뽑으려는 값이 없는 경우 2번과 3번 연산 중 어느것이 더 최솟값을 구할수 있는지 판단해야 된다.

찾으려는 원소가 위치하는 인덱스(idx)가 "size - idx"보다 작으면 2번 연산을 수행하는 방식이 빠르다. 

---> 이 말이 이해가 잘 안됨

// 2번:왼쪽으로 한 칸 이동
if (idx < DQ.size() - idx) {
    DQ.push_back(DQ.front());
    DQ.pop_front();
}
else {
    // 3번:오른쪽으로 한 칸 이동
    DQ.push_front(DQ.back());
    DQ.pop_back();
}