[伯俊]AC#5430
説明:
Deque資料構造を用いて解答を行った.方向変数を設定し,最後に逆戻り,順戻りの方式を用いた.
最初は問題の要求が10万*1001000万くらいなら普通に並ぶこともできると思っていたのですが、ゴールド難易度の問題かもしれないのでタイムアウト.白俊はどこまで通過できるか分からない.
Node.説明する
Deque資料構造を用いて解答を行った.方向変数を設定し,最後に逆戻り,順戻りの方式を用いた.
最初は問題の要求が10万*1001000万くらいなら普通に並ぶこともできると思っていたのですが、ゴールド難易度の問題かもしれないのでタイムアウト.白俊はどこまで通過できるか分からない.
Node.説明する
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
class Node {
prev = null;
next = null;
constructor(value) {
this.value = value;
}
}
class Deque {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push_front(value) {
const newNode = new Node(value);
if (this.empty()) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.length += 1;
}
push_back(value) {
const newNode = new Node(value);
if (this.empty()) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length += 1;
}
pop_front() {
if (this.empty()) return -1;
const front = this.front();
this.head = this.head.next;
this.length -= 1;
return front;
}
pop_back() {
if (this.empty()) return -1;
const back = this.back();
this.tail = this.tail.prev;
this.length -= 1;
return back;
}
size() {
return this.length;
}
empty() {
return this.length === 0 ? 1 : 0;
}
front() {
if (this.empty()) return -1;
return this.head.value;
}
back() {
if (this.empty()) return -1;
return this.tail.value;
}
*[Symbol.iterator]() {
let tmp = this.head;
for (let i = 0; i < this.size(); i++) {
yield tmp.value;
tmp = tmp.next;
}
}
}
const solution = (commands, n, nums) => {
const deque = new Deque();
nums.forEach((num) => deque.push_back(num));
let direction = 0; // 0 정방향, 1: 역방향
for (const command of commands) {
if (command === 'R') {
direction = (direction + 1) % 2;
} else if (command === 'D') {
if (deque.empty()) return 'error';
if (direction === 0) deque.pop_front();
else deque.pop_back();
}
}
const arr = [...deque];
if (direction === 1) arr.reverse();
return JSON.stringify(arr);
};
const N = Number(input[0]);
for (let i = 0; i < N; i++) {
const [commands, n, numsStr] = input.slice(1 + i * 3, 4 + i * 3);
console.log(solution(commands, n, JSON.parse(numsStr)));
}
C++プール#include <bits/stdc++.h>
using namespace std;
string solution(string commands, deque<int> DQ) {
bool isReversed = false;
for (auto command : commands) {
if (command == 'R') {
isReversed = !isReversed;
}
else if(command == 'D') {
if (DQ.empty()) return "error";
if (isReversed) DQ.pop_back();
else DQ.pop_front();
}
}
string answer = "[";
if (isReversed) {
for (auto o = DQ.rbegin(); o != DQ.rend(); o++) {
answer += to_string(*o) + ',';
}
} else {
for (auto num : DQ) {
answer += to_string(num) + ",";
}
}
if (answer[answer.length() - 1] == ',') answer.pop_back();
answer += "]";
return answer;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
while(N--) {
string commands; cin >> commands;
int M; cin >> M;
string nums; cin >> nums;
deque<int> DQ;
string tmp = "";
for (int i=0; i<nums.length(); i++) {
if (isdigit(nums[i])) {
tmp += nums[i];
} else {
if (!tmp.empty()) {
DQ.push_back(stoi(tmp));
tmp = "";
}
}
}
cout << solution(commands, DQ) << '\n';
}
return 0;
}
Reference
この問題について([伯俊]AC#5430), 我々は、より多くの情報をここで見つけました https://velog.io/@ahu8867/백준-AC-5430テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol