(javascript) 표 편집

https://school.programmers.co.kr/learn/courses/30/lessons/81303?language=javascript

프로그래머스

 

효율성 테스트가 있어서 은근한 압박감이 있는 문제였다

 

특히나 연결 리스트를 구현하는게 오랜만이라 당황스러웠다.

 

문제 자체는 이해하기 어려운 내용은 아니었다. 단순한 구현 문제로 보인다.

 

첫번째 풀이(배열)

  문제를 풀기 위해 각 인덱스의 행이 삭제되었는지를 체크하는 배열 valid와 삭제된 행들을 저장하는 스택 stack을 만든다.

 행을 삭제하거나 추가할 때마다 이 배열의 값을 수정해준다.

 예를 들어 현재 위치가 3일 때 삭제 명령을 받는다면 valid[3] = false; 를 해준다. 그리고 stack에 삭제된 행의 번호를 넣는다.

 행을 복구하는 명령을 받았을 때는 stack에서 숫자를 하나 pop해서 valid[n] = true; 로 처리해준다.

 

 표를 배열로 표현했을 때 위, 아래 이동 명령은 O(N)의 시간이 걸린다. 최악의 경우 한번 이동하는데도 모든 삭제된 행들을 탐색해야하기 때문이다.

 그리고 삭제 명령은 O(N)이 걸린다. 왜냐면 행을 삭제하고 다음 행으로 이동하는 작업을 수행해야 하는데, 다음 행이 이미 삭제되었는지 아닌지를 확인하면서 최악의 경우 모든 행을 탐색해야하기 때문이다.

 예를 들어, n이 10이고, 1~8까지의 모든 행을 삭제하고 마지막으로 1행을 삭제하려 할 때, 표에 남아있는 9행을 찾기 위해 2~8행을 모두 탐색해야한다. 만약 현재 행이 맨 끝 행이라면 반대로 위쪽으로도 탐색을 해줘야한다.

 복구 명령은 O(1)이 걸린다.

 

 배열을 기반으로 제출했을 때도 효율성 테스트의 절반 정도는 통과가 됐다. 하지만 나머 절반에서 시간 초과가 발생했다.

 따라서 다른 방법으로 문제를 풀어야했다.

 

두번째 풀이(연결리스트)

 두번째 방법은 표를 배열이 아닌 연결 리스트로 표현하는 것이었다.

 nodes라는 배열을 만들고, { index, prev, next, valid } 값을 가지는 노드들을 저장한다.

 index는 nodes 배열에서 node의 인덱스, prev는 이전 노드, next는 다음 노드, valid는 표에서 행이 살아있는지 체크하는 변수이다.

 이동 명령은 x번 이동하는데 O(x)의 시간이 걸린다. 배열로 구현했을 때와는 다르게 이미 삭제된 행들은 탐색하지 않기 때문이다.

 삭제 명령도 O(1) 시간만에 처리가 가능하다. 현재 노드와 인접 노드의 prev와 next만 수정해주면 되기 때문이다.

 복구 명령도 O(1) 시간에 처리할 수 있다. 복구 명령은 항상 마지막으로 삭제됐던 노드를 복구하기 때문에 복구할 노드의 위치를 찾기위한 작업이 필요없다. 행을 삭제할 때 행의 prev와 next 정보가 그대로 보존되기 때문에 이를 참고해서 한번에 복구할 수 있다.

 

 연결 리스트 기반으로 풀었을 때 효율성 테스트를 통과할 수 있었다.

 

코드

function solution(n, k, cmd) {
    var answer = '';
    var nodes = new Array(n);
    var stack = new Array();

    for (var i = 0; i < n; i++) {
        var newNode = { index: i, prev: null, next: null, valid: true };
        nodes[i] = newNode;
        if (i > 0) {
            newNode.prev = nodes[i - 1];
            nodes[i - 1].next = newNode;
        }
    }

    var current = nodes[k];

    for (var i = 0; i < cmd.length; i++) {
        var [command, num] = cmd[i].split(" ");
        num = +num;
        switch (command) {
            case "U":
                for (var t = 0; t < num; t++) {
                    current = current.prev;
                }
                break;
            case "D":
                for (var t = 0; t < num; t++) {
                    current = current.next;
                }
                break;
            case "C":
                stack.push(current.index);
                current.valid = false;
                if (current.next === null) {
                    current.prev.next = null;
                    current = current.prev;
                } else if (current.prev === null) {
                    current.next.prev = null;
                    current = current.next;
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                    current = current.next;
                }
                break;
            case "Z":
                var z = stack.pop();
                nodes[z].valid = true;
                if (nodes[z].prev !== null)
                    nodes[z].prev.next = nodes[z];
                if (nodes[z].next !== null)
                    nodes[z].next.prev = nodes[z];
                break;
        }
    }

    for (var i = 0; i < nodes.length; i++) {
        if (nodes[i].valid) {
            answer += "O";
        } else {
            answer += "X";
        }
    }
    return answer;
}