백준 13417 카드문자열 | JavaScript 객체 key를 기준으로 정렬하기

https://www.acmicpc.net/problem/13417

덱의 삽입/삭제 동작은 10866번 덱에서 구현한 걸 사용했다.

  for (let i = 0; i < n; i++) {
    if (q.deque[q.start.toString()] >= strings[i]) {
      q.push_front(strings[i]);
    } else {
      q.push_back(strings[i]);
    }
  }

왼쪽, 오른쪽 중 어디에 값을 삽입할지는 간단하게 구현할 수 있다.

가장 왼쪽에 있는 값과 새로 삽입할 값을 비교해서 삽입할 값이 작거나 같다면 왼쪽에, 크다면 오른쪽에 삽입하면 된다.
첫번째 카드는 덱에 추가된 값이 없어 else문으로 빠지고 0번 인덱스에 추가된다.

{ '0': 'B',
  '1': 'C',
  '2': 'B',
  '-1': 'A',
  '-2': 'A',
  '-3': 'A'
}

그렇게 값을 전부 삽입하고 나면 이런 객체가 완성된다. 인덱스 숫자대로 정렬을 하면 문제가 원하는 문자열을 만들 수 있지만,,, 객체는 value를 기준으로 정렬된다

이 문제를 해결하기 위해서는 아래의 과정을 거쳐야 한다.

1. 객체에서 key값을 추출한 새로운 배열을 만들고

  Object.keys(q.deque)

2. 해당 배열을 정렬한다.

  sort((a, b) => a - b)

3. 정렬한 key값에 대해 객체의 value를 매핑한다.

  map((key) => q.deque[key]);

화살표함수의 리턴값으로 value만 주고 있기 때문에, 만들어지는 배열은 key값을 기준으로 정렬된 value 배열이다.

sort 함수에 대해서는 이 게시물에 자세히 작성해두었으니 참고하면 좋을 것이다.

전체 코드

class Deque {
  constructor() {
    this.deque = {};
    this.start = 0;
    this.end = 0;
  }

  push_front(x) {
    this.start--;
    this.deque[this.start] = x;
  }

  push_back(x) {
    this.deque[this.end++] = x;
  }
}

function solution(n, strings) {
  let q = new Deque();

  for (let i = 0; i < n; i++) {
    console.log(q.deque[q.start.toString()]);
    console.log(strings[i]);
    console.log(q.deque[q.start.toString()] >= strings[i]);

    if (q.deque[q.start.toString()] >= strings[i]) {
      q.push_front(strings[i]);
    } else {
      q.push_back(strings[i]);
    }
  }

  return Object.keys(q.deque)
    .sort((a, b) => a - b)
    .map((key) => q.deque[key]);
}

// =====입출력=====

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
let t = null;

rl.on("line", (line) => {
  input.push(line);

  if (t === null) {
    t = parseInt(input[0]);
  }

  if (t !== null && input.length === 1 + t * 2) {
    rl.close();
  }
});

rl.on("close", () => {
  let idx = 1;
  for (let i = 0; i < t; i++) {
    const n = parseInt(input[idx++]);
    const strings = input[idx++].trim().split(" ");
    console.log(solution(n, strings).join(""));
  }
});