[프로그래머스 lev3/JS] 표 편집

문제 출처

프로그래머스 le3 - 표 편집

나의 풀이 (실패)

ch 배열을 하나 만들고
그 안에서 index인 k를 움직이며 답을 찾으려 했으나, 정확하지 않았다. 시간초과도 발생했다.

function solution(n, k, cmd) {
  let ch = new Array(n).fill(true);
  let dlt = [];

  cmd.forEach((c) => {
    let [com, _, amt] = c.split("");

    if (com === "U") {
      while (amt) {
        k--;
        if (ch[k]) amt--;
      }
    } else if (com === "D") {
      while (amt) {
        k++;
        if (ch[k]) amt--;
      }
    } else if (com === "C") {
      ch[k] = false;
      dlt.push(k);
      let flag = false;

      for (let i = k + 1; i < ch.length; i++) {
        if (ch[i]) {
          k = i;
          flag = true;
          break;
        }
      }
      if (!flag) k--;
    } else if (com === "Z") {
      let rvt = dlt.pop();
      ch[rvt] = true;
    }
  });

  return ch.map((v) => (v == true ? "O" : "X")).join("");
}

console.log(
  solution(8, 2, ["D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z"])
); // "OOOOXOOO"

다른 풀이

나는 배열의 메서드를 사용해서 cmd를 처리하려 했다.
예를 들어, splice, push, pop 등의 메서드를 사용했는데,
삭제하거나 되돌릴 때 정확한 연결 관계를 표현하는 데 있어 배열 메서드로는 복잡했다.
게다가 진짜 문제는 시간이 너무 오래 소요된다는 점이었다.

배열 메서드들을 사용하면
특히 splice 메서드를 사용하면,
매번 배열을 순회해야 한다.
매번 연결관계를 업데이트하기 위해 불필요하게 배열을 반복해야 한다. 하지만 연결리스트를 생성하면 next, prev 값만 없데이트해주면 된다. 불필요한 배열 반복을 할 필요가 없어지는 셈이다. 이래서 연결리스트를 배우는 구나! 깨닫는 기회였다.

원본 배열의 순서를 찾아야 하므로 연결리스트의 각 노드에 idx 속성도 추가한다.

양방향 연결리스트 생성 과정(for 반복)을 다음과 같다.

• new 키워드를 사용해서 새로운 노드를 생성한다.
• prevNode의 next로 새로 생성한 노드를 연결하고
• 이번에 새로 생성한 노드가 그 다음 i에서는 prev 값이 되어야 하므로 prevNode에 newNode를 할당한다.
• 시작 위치를 잡기 위해 i가 k일 때 curNode에 newNode를 할당한다.

const Node = function (idx, prevNode) {
  this.idx = idx;
  this.prev = prevNode;
  this.next;
};

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

  // 연결리스트 생성
  let root = new Node(0);
  let curNode = root;
  let prevNode = root;
  for (let i = 1; i < n; i++) {
    const newNode = new Node(i, prevNode);
    prevNode.next = newNode;
    prevNode = newNode;

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

  // command 처리 
  const history = [];
  cmd.map((commandLine) => {
    const [command, count] = commandLine.split(" ");
    let i = 0;
    switch (command) {
      case "U":
        while (i < count && curNode.prev) {
          curNode = curNode.prev;
          i++;
        }
        break;
      case "D":
        while (i < count && curNode.next) {
          curNode = curNode.next;
          i++;
        }
        break;
      case "C":
        history.push(curNode);
        const prev = curNode.prev;
        const next = curNode.next;
        if (prev && next) {
          prev.next = next;
          next.prev = prev;
          curNode = next;
        } else if (prev) {
          prev.next = null;
          curNode = prev;
        } else if (next) {
          next.prev = null;
          curNode = next;
        }
        break;
      case "Z":
        const node = history.pop();
        const prevNode = node.prev;
        const nextNode = node.next;
        if (prevNode) {
          prevNode.next = node;
        }
        if (nextNode) {
          nextNode.prev = node;
        }
        break;
    }
  });

  history.map((node) => answer[node.idx] = "X");
  return answer.join("");
}

다른 풀이 2

2차원 배열 구조([prev, next])를 통해 구현한 연결리스트

let list;
let stack = [];
let answer;

const deleted = (k) => {
    let [pre, next] = [list[k][0], list[k][1]];
    stack.push([k, pre, next]);

    answer[k] = false;

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

    return k;
};

const down = (k, m) => {
    for (let i = 0; i < m; i++) k = list[k][1];
    return k;
};

const up = (k, m) => {
    for (let i = 0; i < m; i++) k = list[k][0];
    return k;
};

const restore = () => {
    const s = stack.pop();
    const [k, pre, next] = [s[0], s[1], s[2]];

    if (pre !== -1) list[pre][1] = k;
    if (next !== -1) list[next][0] = k;

    answer[k] = true;
};

const solution = (n, k, cmd) => {
    list = Array.from({ length: n }, (_, index) => [index - 1, index + 1]);
    answer = Array(n).fill(true);
    list[n - 1][1] = -1;
    for (let c of cmd) {
        let order = c.split(' ');

        switch (order[0]) {
            case 'D':
                k = down(k, order[1]);
                break;
            case 'C':
                k = deleted(k);
                break;
            case 'U':
                k = up(k, order[1]);
                break;
            case 'Z':
                restore();
                break;
        }
    }

    return answer.reduce((a, c, i) => (a += c ? 'O' : 'X'), '');
};

참고

[프로그래머스] 표 편집 / Javascript