[백준] AC #5430

설명

Deque 자료구조를 사용해서 풀었다. direction 변수를 하나 정해놓고 마지막에 역방향이라면 역방향으로 return하고 정방향이면 그대로 return하는 방식을 사용했다.

처음에 문제요건이 10만 * 100 이라 1000만 정도면 일반배열로도 통과되지않을까 했지만 골드난이도 문제여서 그런지 시간초과가 났다. 백준은 어느정도여야 통과되는지 잘모르겠다.

Node.js 풀이

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;
}