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

1. 문제

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

1021번: 회전하는 큐

---

 

2. 문제 풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)

using namespace std;

// deque vs vector

int ans;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	deque<int> dq;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) dq.push_back(i);
	while (m--) {
		int x, idx = 0;
		cin >> x;
		for (int i = 0; i < dq.size(); i++)
			if (dq[i] == x)
				idx = i;

		while (dq.front() != x) {
			if (dq.size() - idx <= dq.size() / 2) {
				int tmp = dq.back();
				dq.pop_back();
				dq.push_front(tmp);
			}
			else {
				int tmp = dq.front();
				dq.pop_front();
				dq.push_back(tmp);
			}
			ans++;
		}
		dq.pop_front();
	}
	cout << ans;
}

---

3. 문제 평가 및 해설

 

시간복잡도를 고려하다가 독특한(?) 풀이를 고민하다가 굉장히 시간이 오래 걸린 문제이다.

 

어차피 시간제한이 2초이니 원초적인 방법을 시도할 걸 그랬다. (while문안에 for문, while문이 들어가는 건 언제나 "시간복잡도 때문에 틀리겠지?" 라는 생각이 드는 것 같다...)

 

문제 해설은 다음과 같다.

 

1. 최소값을 구하는 문제이므로, 매 회차마다 구하려고자 하는 deque 내의 index를 찾아야한다. 이 경우, 그냥 for문을 통해 순차적으로 찾아주면 된다. 나는 index를 순차적으로 찾는 방식이 시간복잡도가 오래 걸릴 것이라 생각해서 다양한 방법을 생각했지만, 결국 실패했다.

 

2. dq.front() == x 일 때 까지, 조건을 기준으로 문제에서 주어진 방법을 반복해준다. 조건은 target index를 deque.size()/2와 비교하면 된다. 단순하게 인덱스가 절반보다 크면 오른쪽으로 가는 방식이 유리할 것이고, 반대로 절반보다 작으면, 왼쪽으로 가는 방식이 유리할 것 이다. 

 

추가적으로, deque와 vector는 굉장히, 굉장히 유사하다. 오히려 상위호환이라는 생각도 드는데, deque는 front에 삽입할 때, O(1)의 시간이 걸리지만, vector은 뒤로 한 칸 씩 이동해야 하기 때문에 , O(n)시간이 걸린다. 그러나 deque가 vector보다 언제나 좋은 것은 아니다. vector은 deque와 다르게 메모리가 연속적이라서 cache hit rate가 좋다. 반면에 deque는 메모리 블럭을 만드는 형식이기 때문에 메모리가 연속적이지는 않다. 또한, 코테에서는 이런 문제가 발생하지 않겠지만 vector의 공간이 꽉 찼을 경우, 공간을 다시 할당하고 채워주어야하는 과정이 필요하지만, deque는 메모리 블럭을 이어붙이는 형식이기 때문에, 이런 과정이 필요치 않다.