[백준] 회전하는 큐
설명
자료구조 Deque
를 사용해서 푸는 문제
JS의 경우 덱이 없어서 완벽한 덱은 아니지만 문제에서 주어진 N은 50보다 작거나 같은 자연수라는 조건 때문에 Array
를 extends하여 심플하게 구현했다.
그리고 필요한 rotate 함수를 파이썬의 덱처럼 멤버변수로 추가하여 문제를 풀었다.
C++의 경우 rotate 함수가 없는 것과 index를 찾기 위해 일일히 덱을 순회한 점이 불편했다...
Node.js 풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// test
const input = `10 10
1 6 3 2 7 9 8 4 10 5`
.trim()
.split('\n');
const [N, M] = input[0].split(' ').map(Number);
const orders = input[1].split(' ').map(Number);
class Deque extends Array {
front() {
return this[0];
}
back() {
return this[this.length - 1];
}
popLeft() {
return this.shift();
}
rotate(idx) {
if (idx > 0) {
while (idx--) this.unshift(this.pop());
} else {
while (idx++) this.push(this.shift());
}
}
}
const solution = (N, M, orders) => {
const deque = new Deque();
let count = 0;
for (let i = 1; i <= N; i++) deque.push(i);
orders.forEach((order) => {
const idx = deque.indexOf(order);
if (idx === 0) deque.popLeft();
else {
if (idx <= Math.floor(deque.length / 2)) {
deque.rotate(-idx);
deque.popLeft();
count += idx;
} else {
deque.rotate(deque.length - idx);
count += deque.length - idx;
deque.popLeft();
}
}
});
return count;
};
console.log(solution(N, M, orders));
C++ 풀이
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
deque<int> DQ;
for (int i=1; i<=N; i++) DQ.push_back(i);
int cnt = 0;
int left, right;
for (int i=0; i<M; i++) {
int num; cin >> num;
for (int j=0; j<DQ.size(); j++) {
if (DQ[j] == num) {
left = j;
right = DQ.size() - left;
break;
}
}
if (left < right) {
cnt += left;
while(left--) {
DQ.push_back(DQ.front());
DQ.pop_front();
}
DQ.pop_front();
} else {
cnt += right;
while(right--) {
DQ.push_front(DQ.back());
DQ.pop_back();
}
DQ.pop_front();
}
}
cout << cnt << '\n';
return 0;
}
Author And Source
이 문제에 관하여([백준] 회전하는 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ahu8867/백준-회전하는-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)