[0x07] 덱(Deque)

원소의 추가/제거 O(1)

제일 앞/뒤 원소 확인이 O(1)

나머지 원소들의 확인/변경이 원칙적으로 불가능 하지만 c++ STL deque에서는 인덱스로 원소에 접근할 수 있음

 

양쪽 끝에서 삽입과 삭제가 모두 가능하다.

Double ended Queue라는 뜻을 가지고 있음.

양방향 큐라는 느낌보다는 vector랑 비슷한데, front에도 O(1)에 추가/제거가 가능한 느낌임

deque은 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않다.

 

연습 문제

 

1021: 회전하는 큐

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

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	int n, m;
	int answer = 0;

	deque<int> rq;
	deque<int> nums;

	cin >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		int data;
		cin >> data;
		nums.push_back(data);
	}

	for (int i = 1; i <= n; ++i)
	{
		rq.push_back(i);
	}

	for (int num : nums)
	{
		// algorithm 헤더에 포함. 값을 찾으면 해당 위치의 iterator를 반환. 못찾으면 end.
		// 여기에 begin을 빼면 인덱스를 알 수 있음.
		int idx = find(rq.begin(), rq.end(), num) - rq.begin();
		while (num != rq.front())
		{
			// 왼쪽으로 밀기
			if (idx < (int)rq.size() - idx)
			{
				rq.push_back(rq.front());
				rq.pop_front();
			}
			else
			{
				rq.push_front(rq.back());
				rq.pop_back();
			}
			answer++;
		}
		rq.pop_front();
	}

	cout << answer;

	return 0;
}

 

접근은 괜찮게 했는데 나는 인덱스를 왼쪽으로 밀면 +1, 오른쪽으로 밀면 -1인 누적값을 하나 사용해서 덱사

이즈/2에 더해줘서 구해줬더니 정답이 아니길래 해답을 봤음.

코드 딱 두줄 추가하고 정답처리 받긴 했는데 좀 아쉽다.