[프로그래머스] 카카오 - 표 편집

문제

2021 카카오 채용연계형 인턴십 - 표 편집

https://school.programmers.co.kr/learn/courses/30/lessons/81303

 

 

풀이

설명

모든 명령어를 수행한 후의 표의 상태를 구하는 문제입니다. 행이 삭제되지 않으면 'O', 삭제되면 'X'로 표시됩니다.

 

행의 상태를 저장할 배열을 사용합니다. 모든 행이 활성 상태이므로, 초기값은 'O'로 설정합니다.

삭제된 행을 파악하기 위해 스택을 사용합니다. 인덱스를 저장하여 복구 작업을 효율적으로 처리할 수 있습니다.

 

가장 중요한 부분은 테이블을 어떻게 구성하느냐입니다.

테이블은 삭제되지 않은 행들을 쉽게 관리하기 위해 이중 연결 리스트로 구성합니다. 이 구조는 각 행이 삭제되지 않은 이전 행과 다음 행을 가리키므로, 빠른 탐색, 삭제 및 삽입이 가능합니다. 이중 연결 리스트는 노드로 이루어진 배열로 구현해, 인덱스를 통해 빠르게 접근할 수 있게 합니다.

 

예시 코드

class Node {
  constructor(index) {
    this.index = index;
    this.prev = null;
    this.next = null;
  }
}

function solution(n, k, cmd) {
  const ACTIVE = "O";
  const INACTIVE = "X";
  const COMMANDS = {
    UP: "U",
    DOWN: "D",
    DELETE: "C",
    ROLLBACK: "Z",
  };

  const table = Array.from({ length: n }, (_, i) => new Node(i));
  const activationStatus = Array(n).fill(ACTIVE);
  const deletedRowIndexes = [];
  let currentRow = table[k];

  for (let i = 0; i < n; i++) {
    if (i > 0) table[i].prev = table[i - 1];
    if (i < n - 1) table[i].next = table[i + 1];
  }

  for (let i = 0; i < cmd.length; i++) {
    const [command, steps] = cmd[i].split(" ");

    switch (command) {
      case COMMANDS.UP: {
        currentRow = getRowAboveBySteps(currentRow, steps);
        break;
      }
      case COMMANDS.DOWN: {
        currentRow = getRowBelowBySteps(currentRow, steps);
        break;
      }
      case COMMANDS.DELETE: {
        deleteRow(currentRow);
        currentRow = getNextRow(currentRow);
        break;
      }
      case COMMANDS.ROLLBACK: {
        rollbackRow();
        break;
      }
    }
  }

  return activationStatus.join("");

  function getRowAboveBySteps(row, steps) {
    for (let i = 0; i < steps; i++) {
      row = row.prev;
    }

    return row;
  }

  function getRowBelowBySteps(row, steps) {
    for (let i = 0; i < steps; i++) {
      row = row.next;
    }

    return row;
  }

  function deleteRow(row) {
    activationStatus[row.index] = INACTIVE;
    deletedRowIndexes.push(row.index);

    if (row.prev) row.prev.next = row.next;
    if (row.next) row.next.prev = row.prev;
  }

  function getNextRow(row) {
    return row.next ? row.next : row.prev;
  }

  function rollbackRow() {
    const lastDeletedRow = deletedRowIndexes.pop();
    activationStatus[lastDeletedRow] = ACTIVE;
    const row = table[lastDeletedRow];
    if (row.prev) row.prev.next = row;
    if (row.next) row.next.prev = row;
  }
}