프로그래머스 LEVEL 3(표 편집)

사용 언어 : javascript
해결 날짜 : 2023-04-30
해결 방법 :
- 양방향 연결 리스트를 활용하여 문제 해결
  - 시작부터 끝까지 양방향 연결 리스트로 양쪽 연결
  - cmd를 돌며
    - ‘U’인 경우 X만큼 prev로 이동
    - ‘D’인 경우 X만큼 next로 이동
    - ‘C’인 경우
      - deleted 배열에 push
      - 현재 노드의 prev와 next를 이어주되, 없다면 null로 연결
    - ‘Z’인 경우
      - deleted 배열에서 pop
      - pop한 Node 연결
  - 최종적으로 deleted 속 index만 ‘X’로 변경

회고 :

처음에 작성한 코드

function solution(n, k, cmd) {
  const answer = Array.from({ length: n }, () => 'O');
  let cursor = k;
  let deleted = [];

  cmd.forEach((command, i) => {
    const [C, X] = command.split(' ');

    switch (C) {
      case 'U':
        cursor -= parseInt(X, 10);
        break;
      case 'D':
        cursor += parseInt(X, 10);
        break;
      case 'C':
        const length = n - deleted.length;
        deleted.push(cursor);

        if (cursor === length) {
          cursor -= 1;
        }
        break;
      case 'Z':
        deleted.pop();
        break;
      default:
        break;
    }
  });

  deleted.forEach((v) => {
    answer[v] = 'X';
  });

  return answer.join('');
}

표에서 삭제하고 복구할 때 커서의 값이 변할 수 있다는 점을 고려하지 못했다.
따라서 이를 고려하기 위해 양방향으로 연결할 필요가 있다고 생각해 양방향 연결 리스트를 적용하였다.

코드

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

function solution(n, k, cmd) {
  const answer = Array.from({ length: n }, () => 'O');

  let currentNode = new Node(0),
    prevNode = currentNode;

  for (let i = 1; i < n; i++) {
    const newNode = new Node(i, prevNode);
    prevNode.next = newNode;
    prevNode = newNode;

    if (i === k) {
      currentNode = newNode;
    }
  }

  const deleted = [];

  cmd.forEach((command) => {
    const [C, X] = command.split(' ');
    let i = 0;

    switch (C) {
      case 'U':
        while (i < parseInt(X, 10) && currentNode.prev) {
          currentNode = currentNode.prev;
          i++;
        }
        break;
      case 'D':
        while (i < parseInt(X, 10) && currentNode.next) {
          currentNode = currentNode.next;
          i++;
        }
        break;
      case 'C':
        deleted.push(currentNode);
        const prev = currentNode.prev,
          next = currentNode.next;

        if (prev && next) {
          prev.next = next;
          next.prev = prev;
          currentNode = next;
        } else if (prev) {
          prev.next = null;
          currentNode = prev;
        } else if (next) {
          next.prev = null;
          currentNode = next;
        }

        break;
      case 'Z':
        const restored = deleted.pop();
        const restoredPrev = restored.prev,
          restoredNext = restored.next;

        if (restoredPrev) {
          restoredPrev.next = restored;
        }

        if (restoredNext) {
          restoredNext.prev = restored;
        }

        break;
      default:
        break;
    }
  });

  deleted.forEach((d) => {
    answer[d.index] = 'X';
  });

  return answer.join('');
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges