[Javascript][Programmers] 표 편집 - 2021 카카오 채용연계형 인턴십

 

문제

문제 해결을 위한 아이디어를 떠올리는 것은 어렵지 않습니다. 가장 직관적인 방법은 주어진 배열을 그대로 사용하는 것입니다. 이 접근 방식은 이해하기 쉽고 구현하기도 간단합니다. 하지만, 이 방법은 데이터를 삽입하거나 삭제할 때 매우 비효율적입니다.

 

이러한 비효율성을 해결하기 위해 이중 연결 리스트(Doubly Linked List)를 사용할 수 있습니다. 이중 연결 리스트는 각 노드가 앞뒤 노드를 모두 참조하는 구조로, 데이터의 삽입과 삭제가 매우 효율적입니다. 새 요소를 추가하거나 기존 요소를 제거할 때, 단순히 인접한 노드들의 참조만 수정하면 되므로 O(1)의 시간 복잡도로 작업을 수행할 수 있습니다.

 

또한, 해당 문제에는 복구 명령어가 존재하는데 스택을 사용하여 구현할 수 있습니다.

 

나의 풀이

• 시간복잡도: O(N)

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

function solution(n, k, cmd) {
    // 연결 리스트 초기화
    let current = new Node(0);
    let root = current;
    for (let i = 1; i < n; i++) {
        let newNode = new Node(i);
        current.next = newNode;
        newNode.prev = current;
        current = newNode;
    }

    // k번째 노드로 이동
    current = root;
    for (let i = 0; i < k; i++) {
        current = current.next;
    }

    const stack = [];
    const deleted = new Array(n).fill(false);

    for (const command of cmd) {
        const [action, value] = command.split(' ');

        switch (action) {
            case 'U':
                for (let i = 0; i < parseInt(value); i++) {
                    current = current.prev;
                }
                break;
            case 'D':
                for (let i = 0; i < parseInt(value); i++) {
                    current = current.next;
                }
                break;
            case 'C':
                stack.push(current);
                deleted[current.data] = true;
                
                const prev = current.prev;
                const next = current.next;
                
                if (prev) prev.next = next;
                if (next) next.prev = prev;
                
                // 마지막 행인 경우, 윗 행 선택
                if (!next) {
                    current = prev;
                } else {
                    current = next;
                }
                break;
            case 'Z':
                const restored = stack.pop();
                deleted[restored.data] = false;
                
                const prevNode = restored.prev;
                const nextNode = restored.next;
                
                if (prevNode) prevNode.next = restored;
                if (nextNode) nextNode.prev = restored;
                break;
        }
    }

    return deleted.map(d => d ? 'X' : 'O').join('');
}

 

다른 풀이

• 시간복잡도: O(N)

노드 객체를 사용하지 않고 인덱스만을 사용하여 유사한 기능을 구현할 수도 있습니다.

function solution(n, k, cmd) {
  // ➊ 삭제된 행의 인덱스를 저장하는 리스트
  const deleted = [];

  // ➋ 링크드 리스트에서 각 행 위아래의 행의 인덱스를 저장하는 리스트
  const up = [...new Array(n + 2)].map((_, i) => i - 1);
  const down = [...new Array(n + 1)].map((_, i) => i + 1);

  // ➌ 현재 위치를 나타내는 인덱스
  k += 1;

  // ➍ 주어진 명령어(cmd) 리스트를 하나씩 처리
  for (const item of cmd) {
    // ➎ 현재 위치를 삭제하고 그다음 위치로 이동
    if (item.startsWith("C")) {
      deleted.push(k);
      up[down[k]] = up[k];
      down[up[k]] = down[k];
      k = n < down[k] ? up[k] : down[k];
    }

    // ➏ 가장 최근에 삭제된 행을 복원
    else if (item.startsWith("Z")) {
      const restore = deleted.pop();
      down[up[restore]] = restore;
      up[down[restore]] = restore;
    }

    // ➐ U 또는 D를 사용해 현재 위치를 위아래로 이동
    else {
      const [action, num] = item.split(" ");
      if (action === "U") {
        for (let i = 0; i < num; i++) {
          k = up[k];
        }
      } else {
        for (let i = 0; i < num; i++) {
          k = down[k];
        }
      }
    }
  }

  // ➑ 삭제된 행의 위치에 'X'를, 그렇지 않은 행의 위치에 'O'를 포함하는 문자열 반환
  const answer = new Array(n).fill("O");
  for (const i of deleted) {
    answer[i - 1] = "X";
  }
  return answer.join("");
}

 

---

Reference

코딩테스트 합격자되기: 자바스크립트 편