[프로그래머스] 표 편집 | 자바스크립트 | 2021 카카오 채용연계형 인턴십 | Lv.3

문제

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

코딩테스트 연습 - 표 편집

 

풀이

function solution(n, k, cmd) {
  const stack = [];
  const answer = Array.from({ length: n }, () => "O");
  const list = Array.from({ length: n }, (_, index) => [index - 1, index + 1]);
  list[n - 1][1] = -1;

  function upNode(k, row) {
    for (let i = 0; i < row; i++) k = list[k][0];
    return k;
  }

  function downNode(k, row) {
    for (let i = 0; i < row; i++) k = list[k][1];
    return k;
  }

  function deleteNode(k) {
    const [prev, next] = list[k];
    stack.push([k, prev, next]);
    answer[k] = "X";

    if (next === -1) {
      if (prev !== -1) list[prev][1] = next;
      k = prev;
    } else {
      list[next][0] = prev;
      if (prev !== -1) list[prev][1] = next;
      k = next;
    }
    return k;
  }

  function restoreNode() {
    const [node, prev, next] = stack.pop();
    if (prev !== -1) list[prev][1] = node;
    if (next !== -1) list[next][0] = node;
    answer[node] = "O";
  }

  for (const item of cmd) {
    const [direct, row] = item.split(" ");
    switch (direct) {
      case "D":
        k = downNode(k, +row);
        break;
      case "U":
        k = upNode(k, +row);
        break;
      case "C":
        k = deleteNode(k);
        break;
      case "Z":
        restoreNode();
        break;
    }
  }
  return answer.join("");
}

---

이 문제는 양방향 연결 리스트를 사용해야 효율성까지 통과하는 문제인 것 같다.. 

function upNode(k, row) {
    for (let i = 0; i < row; i++) k = list[k][0];
    return k;
}

k의 위치를 위로 올리는 함수부터 보자. row에는 얼만큼 올려야 하는 지 숫자가 들어온다.
예를 들어 3만큼 올리려면, 3번 반복하면서 현재 k위치가 가리키는 prev를 k에 대입해준다. 그렇게 3번 반복하면 k의 현재 위치는 3번째 위에 있는 노드가 될 것이다. downNode 함수도 이와 같은 방식이다.
중요한 것은 deleteNode와 restoreNode 함수이다.

function deleteNode(k) {
    const [prev, next] = list[k];
    stack.push([k, prev, next]);
    answer[k] = "X";

    if (next === -1) {
      if (prev !== -1) list[prev][1] = next;
      k = prev;
    } else {
      list[next][0] = prev;
      if (prev !== -1) list[prev][1] = next;
      k = next;
    }
    return k;
}

next가 1인 경우는 마지막 행을 뜻하므로 k를 이전 행으로 변경해준다. 그리고 prev가 -1이 아닌 경우 (행이 한개인 경우가 아닐 경우), 이전 행의 next는 -1이 된다.

next가 1이 아닌 경우는 마지막 행이 아닐 때이다. next가 가리키는 prev를 현재의 prev로 변경해주고, prev의 다음 값이 현재의 next가 되도록 변경해준다. 그리고 k를 다음 행으로 넘긴다.

이제 restoreNode함수를 보자.

function restoreNode() {
    const [node, prev, next] = stack.pop();
    if (prev !== -1) list[prev][1] = node;
    if (next !== -1) list[next][0] = node;
    answer[node] = "O";
}

가장 최신의 행을 스택에서 pop한다. if으로 모두 예외 처리를 해주고, prev의 다음 값을 현재 행으로, next의 이전 값을 현재 행으로 바꿔주고 answer의 node위치를 O로 변경해준다 !

 

자료구조 때 배웠던 양방향 연결 리스트를 다시 한번 복습했다..🙃