[Beakjoon][#1021] 회전하는 큐

• [ 장르 ] deque
• [ 문제 ]

1021번: 회전하는 큐

• My Code

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;
int main()
{
	int queSize, selectCnt,want,answer = 0;
	deque<int> dq;
	vector<int> element;

	cin >> queSize >> selectCnt;
	for (int i = 0; i < queSize; i++)
		dq.push_back(i + 1);

	for (int i = 0; i < selectCnt; i++)
	{
		cin >> want;
		element.push_back(want);
	}

	for (int i = 0; i < selectCnt; i++)
	{
		
		if (element[i] == dq.front())
			dq.pop_front();
		else
		{
			int index = find(dq.begin(), dq.end(), element[i]) - dq.begin();	// ★
			if (index <= dq.size() - index)
			{
			//	cout << index << endl;
				while (dq.front() != element[i])
				{
					dq.push_back(dq.front());
					dq.pop_front();
					answer++;
				}
			}
			else
			{
			//	cout << index << endl;
				while (dq.front() != element[i])
				{
					dq.push_front(dq.back());
					dq.pop_back();
					answer++;
				}
			}
			dq.pop_front();
		}
		//for (auto iter = dq.begin(); iter != dq.end(); iter++)
			//cout << *iter << ' ';
		//cout << endl;
	}
	cout << answer << endl;
	return 0;
}

 " find( ) 함수의 형식과 리턴 값을 잘 인지하자. "

• [ CheckPoint ]

• 처음에는 문제가 어떤 걸 원하는지 제대로 이해를 못했다. 문제가 "회전하는 큐"라서 원형 큐를 쓰면 되는 건가 생각했다.
  
• 이 문제가 묻는 것은 원소의 값이 무엇인지는 상관없다. 단지 처음 큐에서 2번째 줄에 입력되는 원소의 위치 순서에 대해 우선순위를 주고
  이 우선순위에 따라서 첫번째 원소를 뽑아내는 과정에서 왼쪽 오른쪽 이동 연산을 몇번하는지 Count하는게 문제이다.
  이렇게 말해놓고 나도 뭔소린지 이해 못한다. 그냥 이 첨부자료를 보는 것이 좋겠다.
  
• 문제가 어느정도 이해가 가면, 이건 맨 앞에 요소를 뽑아 낼 때만, Count가 누적이 안되고, queue의 범위가 줄어들기 때문에 queue에서
  매 차례 원하는 원소를 뒤에서든 앞에서든 이동시킬수 있도록 deque를 써야한다는 것을 인지하게 될 것이다.
• 그 다음 포인트는, 문제를 풀다보면, 매 차례 왼쪽(front) 과 오른쪽(back) 방향 중 어느쪽으로 이번 차례에는 pop()을하면서 front로 정답 요소를 이동시켜야 할까이다.
  이것은 문제의 이동연산의 최솟값을 출력하라고 했으니, 매 시점의 deque에서 원하는 원소의 index위치를 구하고 이를 front와 back중에 더 가까운 쪽으로 pop( )하면서 이동하면 된다.
  단, 어찌됬든 원하는 원소는 결국 front에서 pop( )되기 때문에 back 방향으로 pop 을하면서 front로 보낼때는 이동연산을 한번 더 해야하는 것을 알아야한다.
• 결국 우리는 매 과정에서 변화하는 기존에 원소값 인덱스를 찾아야한다. 그렇기 때문에 나는 find( )연산자를 생각했다.
• [ 형식 ]
  find( iterator.begin( ), iterator.end( ), 찾길 원하는 원소 값 ) 
  [ 반환 값 ]
  원소의 위치에 iterator를 반환 !
• 결국 현재 내가 원하는 원소의 "인덱스"를 알고 싶다면, 리턴된 값 - 전체 iterator.begin( )을 해줘야 연산 결과가 인덱스 값이 된다.
  ( 코드의 ★ 부분 참고하길 바란다. )
• 그리고 이 인덱스 값은 0부터가 아닌 1부터임을 알자.