[백준]회전하는 큐
유의할점
풀이
덱을 이용하면 reverse하지 않아도 원소를 빼낼수있다.
원소를 빼는 과정은 2번을 사용하거나 3번을 사용해야한다. 둘이 섞어서 사용하는 경우는 무조건 최적이 아니다.
코드
C++
#include <iostream>
#include <algorithm>
#include <deque>
#include <queue>
using namespace std;
int second(int n, deque<int> &dq) {
int res = 0;
while (dq.front()!=n) {
res++;
dq.push_back(dq.front());
dq.pop_front();
}
dq.pop_front();
return res;
}
int third(int n, deque<int> &dq) {
int res = 0;
while (dq.front()!=n) {
res++;
dq.push_front(dq.back());
dq.pop_back();
}
dq.pop_front();
return res;
}
int main() {
queue<int> q;
deque<int> dq;
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
dq.push_back(i);
}
int M;
cin >> M;
for (int i = 0; i < M; i++) {
int _;
cin >> _;
q.push(_);
}
int res = 0;
while (!q.empty()) {
deque<int> sq = dq;
deque<int> tq = dq;
int i = second(q.front(), sq);
int j = third(q.front(), tq);
if (i > j) {
dq = tq;
res += j;
}
else {
dq = sq;
res += i;
}
q.pop();
}
cout << res;
}
Author And Source
이 문제에 관하여([백준]회전하는 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@6047198844/백준회전하는-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)