![[1021번] 회전하는 큐](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FuDWEx%2FbtqwAIn5NCF%2FHnx8hE3691FFxPnzHRLyt0%2Fimg.png)
반응형
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
www.acmicpc.net
큐(Queue)는 다들 아시죠? 큐의 특징은 FIFO(First In First Out)입니다.
그렇기 때문에 pop하면 무조건 맨 앞 원소가 나오게 되고, push하면 무조건 맨 뒤에 원소가 들어가게 되죠.
하지만 이번에는 이 큐의 오퍼레이션을 추가한 자료구조가 있습니다.
Queue Member Functions: push(value), pop()
바로 덱(Deque)이라고 하는 자료구조입니다.
원소의 pop을 앞뒤 모두 할 수 있고, push 또한 마찬가지입니다.
Deque Member Functions: push_front(value), psuh_back(value), pop_front(), pop_back()
이 문제는 이 덱을 이용하여 푸는 문제입니다. (사실 굳이 덱 아니어도 풀 수 있는...)
1, 2, 3 연산 방법은 미리 정의되어 있고, $N$개의 원소가 이미 덱에 들어가 있습니다. 그리고 pop할 위치를 줍니다.
이때 각 주어진 위치를 pop(1번 연산)하기 위한 2, 3번 연산의 최소 횟수를 구하면 됩니다.
반응형