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

문제

[프로그래머스] 표 편집
(2021 카카오 채용연계형 인턴쉽)

사용 알고리즘

- 연결리스트 (Linked List)

해결방법

문제

• 표의 각 행 정보를 저장하는 Node를 만들고, 해당 노드들을 가지고 linked list를 생성한다
  • Node는 행의 index, 해당 행 이전 행의 index(prev), 다음 행의 index(next)를 갖는다.
• moveSelectedNode (count, direction) : 명령어 U, D 사용
  • direction (prev, next) 방향으로 count 만큼 이동하여 select 된 Node를 변경
• deleteNode : 명령어 C 사용
  • 현재 select된 Node를 cStack에 따로 저장 후
  • 해당 Node의 prevNode의 next, 해당 Node의 nextNode의 prev를 갱신
• recoverNode : 명령어 Z 사용
  • delete와 반대로 삭제되어 cStack에 분리보관됐던 노드를 원복시킴
  • 최근에 삭제된 것 부터 순서대로 원복이며, 해당 노드의 prevNode의 next, 해당 Node의 nextNode의 prev를 갱신

소스코드

사용언어 : Javascript

function solution(n, k, cmd) {
    const Node = function (index, prev) {
        this.index = index;
        this.prev = prev;
        this.next = null;
    };

    let prevNode = new Node(0);
    let select; //선택된 노드

    // 링크드리스트 생성
    for (let i = 1; i < n; i++) {
        const cntNode = new Node(i, prevNode);
        prevNode.next = cntNode;
        prevNode = cntNode;

        // 처음 선택된 노드 저장
        if (i === k) {
          select = cntNode;
        }
    }

    let cStack = [];

    const moveSelectedNode = (count, direction) => {
    for (let i = 0; i < count; i++) {
      if (!select[direction]) break;
          select = select[direction];
        }
    };

    const deleteNode = () => {
        const prev = select.prev;
        const next = select.next;

        cStack.push(select);

        select = next ? next : prev;

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

    const recoverNode = () => {
        const targetNode = cStack.pop();

        const prev = targetNode.prev;
        const next = targetNode.next;

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

    cmd.forEach((c) => {
        switch (c[0]) {
          case "U":
            moveSelectedNode(c.split(" ")[1], "prev");
            break;
          case "D":
            moveSelectedNode(c.split(" ")[1], "next");
            break;
          case "C":
            deleteNode();
            break;
          case "Z":
            recoverNode();
            break;
        }
    });

    let result = Array(n).fill("O");
    cStack.forEach((node) => {
        result[node.index] = "X";
    });
    return result.join("");
}

Javascript Linked List

* Node 를 Function으로 object를 사용해 구현

https://velog.io/@kimkevin90/Javascript%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-Linked-List-%EA%B5%AC%ED%98%84

Javascript를 이용한 Linked List 구현

 

 

foreach

* Array 객체의 메소드 forEach는 for문과 달리 index와 조건식, 증감식 없이 callback함수를 통해 기능을 수행

 

 

한줄평

연결리스트 너무 오랜만이라 기억이 잘 안났는데, 다시 보니까 새록새록하다