백준 18115번

QUESTION LINK

카드가 규칙에 따라 이동해서 만들어진 카드의 최종적인 오름차순 배열 형태를 다시 기존 형태로 되돌려야하는 문제입니다.

5
2 3 3 2 1

예를 들어, 위와 같은 값이 주어졌다고 할 때, 실제로 만들어진 카드의 최종 결과물은 왼쪽이 아래, 오른쪽이 위라고 할 때 아래와 같은 형태를 만들게 됩니다.

[5, 4, 3, 2, 1];

여기서, 기존의 배열로 되돌리기 위해서는 가장 위에 있는 카드, 즉 위 배열의 가장 마지막 요소부터 차례대로 규칙을 반대로 적용해서 문제를 풀어주면 됩니다. 여기서 불필요한 배열을 줄이기 위해 위 예시를 통해 만들어지는 규칙 배열의 index를 활용하기로 했습니다.

const orders = ordersArray.split(" ");
// [2, 3, 3, 2, 1]
const ordersLength = orders.length;
// 각 요소의 ordersLength - index는 실제 카드의 숫자를 나타내게 됨

이를 활용해 순서 배열들을 거꾸로 순회하며, 해당 카드의 규칙 이전 상태로 되돌리는 코드를 아래와 같이 작성했습니다.

const orders = ordersArray.split(" ");
const ordersLength = orders.length;

let target = 1;
// 실제 카드의 숫자
let resultArray = [];
// 결과 배열. index가 클 수록 아래에 있는 것으로 가정

// 카드 숫자가 실제 카드의 개수보다 많아지면 종료
while (target <= orders.length) {
  // 카드의 정해져있던 명령
  const order = orders[ordersLength - target];

  // 1인 경우 배열의 가장 처음으로 옴
  if (order === "1") {
    resultArray = [target, ...resultArray];
  }
  // 2인 경우 배열의 두 번재 자리로 옴
  if (order === "2") {
    resultArray = [resultArray[0], target, ...resultArray.slice(1)];
  }
  // 3인 경우 가장 아래에 배치
  if (order === "3") {
    resultArray.push(target);
  }

  target += 1;
}

const result = resultArray.join(" ");

console.log(result);

위와 같은 코드를 작성하여 예시로 정해져있던 문제들을 모두 해결할 수 있었습니다. 하지만, 이런 식으로 문제를 해결할 경우, ‘시간 초과’가 계속해서 나왔고, 이 문제를 해결하기 위한 방법을 다시 생각해보았습니다.

여기서 이 문제의 기본적인 사용 알고리즘이 ‘덱’이라는 것을 알게 됐습니다. 이를 위해, 자바스크립트로 ‘덱’을 만드는 방법을 다시 고안했습니다.

덱(deque)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조의 형태로, 두 개의 포인터를 사용해 양쪽에서 삭제와 삽입을 발생시킬 수 있습니다. 큐(queue)와 스택(stack)을 합친 형태로 볼 수 있습니다.

// 덱에서 각 노드들의 특징을 담은 클래스
class Node {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

// 실제로 만들어질 덱의 클래스
class Deque {
  // 처음에는 head, tail이 모두 비어있음
  constructor() {
    this.count = 0;
    this.head = null;
    this.tail = null;
  }

  // head에 값을 추가
  putHead(data) {
    const node = new Node(data);
    // 값이 없는 경우, head와 tail이 모두 node로 설정됨
    if (!this.count) {
      this.head = node;
      this.tail = node;
    } else {
      // 이전의 head를 새롭게 지정된 node의 뒷부분으로 보냄
      const prevHead = this.head;
      this.head = node;
      this.head.next = prevHead;
      prevHead.prev = node;
    }

    this.count += 1;
  }

  // tail에 값을 추가
  putTail(data) {
    const node = new Node(data);
    // 값이 없는 경우, head와 tail이 모두 node로 설정됨
    if (!this.count) {
      this.head = node;
      this.tail = node;
    } else {
      // 이전의 tail을 새롭게 지정된 node의 앞부분으로 보냄
      const prevTail = this.tail;
      prevTail.next = node;
      node.prev = prevTail;
      this.tail = node;
    }

    this.count += 1;
  }

  // 이번 문제를 풀기 위해 만들어진 메서드
  putSecond(data) {
    const node = new Node(data);
    // 값이 없는 경우, head와 tail이 모두 node로 설정됨
    if (!this.count) {
      this.head = node;
      this.tail = node;
    } else {
      // 값이 있는 경우, head의 뒤, 기존의 second앞에 배치하도록 설정
      const { head } = this;
      const second = head.next;
      if (!second) {
        this.putTail(data);
      } else {
        node.prev = head;
        node.next = second;
        head.next = node;
        second.prev = node;
        this.count += 1;
      }
    }
  }

  // head를 제거하고 그 다음 값을 head로 설정
  getHead() {
    if (!this.head) return;
    const prevHead = this.head;
    this.head = prevHead.next;
    prevHead.next = null;
    this.count -= 1;
    return data;
  }

  // tail을 제거하고 그 다음 값을 tail로 설정
  getTail() {
    if (!this.tail) return;
    const prevTail = this.head;
    this.tail = prevTail.prev;
    prevTail.prev = null;
    this.count -= 1;
    return data;
  }
}

위와 같은 형태의 덱을 만들고, 이를 문제에 다시 적용해주었습니다.

let target = 1;
const deque = new Deque();

while (target <= orders.length) {
  const order = orders[ordersLength - target];

  if (order === "1") {
    deque.putHead(target);
    // 가장 앞에 추가하므로 putHead 사용
  }
  if (order === "2") {
    deque.putSecond(target);
    // 두 번째 위치에 추가하므로 putSecond 사용
  }
  if (order === "3") {
    deque.putTail(target);
    // 가장 마지막에 추가하므로 putTail 사용
  }

  target += 1;
}

let result = "";
let curNode = deque.head;

while (curNode) {
  result += ` ${curNode.data}`;
  curNode = curNode.next;
}

result = result.slice(1);
// 처음에 만들어진 빈칸 제거

console.log(result);

위와 같은 형태를 사용함으로서 이 문제를 해결할 수 있었습니다. 이번 문제의 경우, 앞 ∙ 뒤로 자료를 추가하는 형태로 문제가 만들어져있었습니다. 이러한 형태의 문제는 큐, 스택을 모두 사용해야 하므로 덱을 사용해야 한다는 것을 알게 됐고, 오래간만에 자바스크립트의 클래스도 사용해볼 수 있는 기회가 되었습니다.

GITHUB  EMAIL