백준 1021번 : 회전하는 큐

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

queue 라이브러리를 사용하자. 자료구조때 많이 만들어 썼다. 그런데 쓰면서 array를 부모 클래스로 받은 queue를 만들껄이라는 후회를 했다. queue가 인덱스 접근에 최악이다.

참고 : https://twpower.github.io/76-how-to-use-queue-in-cpp

와 한번에 맞았다!

다음에도 열심히 잘 짜서 한번에 맞추자

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

void secondfunc(queue<int>& que); 

void thirdfunc(queue<int>& que);

int main() {
	int num, out, answer = 0;
	cin >> num >> out;
	
	queue<int> que;
	for (int i = 1; i <= num; i++) {
		que.push(i);
	}

	int key;
	while (out != 0) {
		int idx = -1;
		cin >> key;

		int total = que.size();
		int mid = (total / 2);
		
		for (int j = 0; j < total; j++) {		
			int elmt = que.front();	
			if (key == elmt)
				idx = j;
			que.pop();
			que.push(elmt);
		}

		if (idx <= mid ) {
			for (int i = 0; i < idx; i++) {
				secondfunc(que);
				answer++;
			}
		}

		else {
			for (int i = idx; i <total; i++) {
				thirdfunc(que);
				answer++;
			}
		}

		que.pop();
		out--;
	}
	cout << answer << endl;
	return 0;
}


void secondfunc(queue<int>& que) {
	int tmp = que.front();
	que.pop();
	que.push(tmp);
}

void thirdfunc(queue<int>& que) {
	int tmp = que.back();
	int num = que.size() - 1;
	queue<int> temp;
	temp.push(tmp);
	int front;
    
	for (int i = 0; i< num; i++) {
		front = que.front();
		temp.push(front);
		que.pop();
	}
	while (!que.empty()) {
		que.pop();
	}
	for (int i = 0; i < num + 1; i++) {
		front = temp.front();
		que.push(front);
		temp.pop();
	}
}

결국 구현은 queue 라이브러리만 사용해서 회전하는 큐의 성질을 제대로 살리지 못했다. circle queue..

for (int j = 0; j < total; j++) {		
    int elmt = que.front();	
    if (key == elmt)
    	idx = j;
    que.pop();
    que.push(elmt);
}

우선 첫번째로 큐라서 인덱스로 접근하지 못한다는 점으로 인해 for문으로 한번 회전시켜서 찾는 아이템의 인덱스를 찾는 방법으로 시작했다. 스택이였다면 추가적으로 큐를 썼어야 했을 듯 싶다. 하지만 큐라서..

//중간보다 앞에 있으면
if (idx <= mid ) {
	for (int i = 0; i < idx; i++) {
		secondfunc(que);
		answer++;
	}
}
//중간보다 뒤에 있으면 
else {
	for (int i = idx; i <total; i++) {
		thirdfunc(que);
		answer++;
	}
}

중간보다 앞에 있다면 2번째 함수가 더 빠르고 중간보다 뒤에 있다면 3번째 함수가 더 빠르다는 점을 이용해 mid 변수를 기준으로 계산하여 각각 적합한 함수를 따라갈 수 있도록 했다.

각각 함수를 먼저 확인해보자.

void secondfunc(queue<int>& que) {
	int tmp = que.front();
	que.pop();
	que.push(tmp);
}

먼저 쉬웠던 두번째 함수. 큐의 기본 함수들만으로도 구현 가능해서 더이상 설명할 필요 없다고 보고.

void thirdfunc(queue<int>& que) {
	int tmp = que.back();
	int num = que.size() - 1;
	queue<int> temp;
	temp.push(tmp);
	int front;
	for (int i = 0; i< num; i++) {
		front = que.front();
		temp.push(front);
		que.pop();
	}
	while (!que.empty()) {
		que.pop();
	}
	for (int i = 0; i < num + 1; i++) {
		front = temp.front();
		que.push(front);
		temp.pop();
	}
}

걱정되었던 세번째 함수. 근데 위에서 인덱스 찾을 때도 그렇고 결국 다 O(N)만 걸리기 때문에 시간 제한은 걱정 안해도 되었을 듯 싶다. 중요했던 것은 큐를 비우는 작업.

while (!que.empty())
	que.pop();

이 부분을 구현하지 않고 진행하였더니 마지막에 count되지 않고 남아있던 element들이 살아남아 que가 더 길어지는 일이 발생했었다. '설마' 하는 마음에 구현하지 않았는데 다음부터는 '그래도' 하는 마음으로 구현해야 겠다는 생각을 했다.

마지막으로 pop은 공통으로 진행되는 진행 순서였으므로 처음에는 함수로 뺐다가 어차피 pop()이니까 내장 함수로 구현했다.

que.pop();
out--;

끝으로 계속해서 out 개수만큼 while이 진행된다.