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

문제 링크

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

코딩테스트 연습 - 표 편집

 

풀이

처음 문제를 봤을 땐 현재 행을 기준으로 위, 아래쪽 스택 두 개를 이용해서 관리하면 안 될까? 하고 생각했습니다.

근데 이러면 Z연산을 구현 못하더라구요..

 

결론부터 말하면 양방향 링크드 리스트를 구현해서 풀 수 있습니다.

1) U, D 연산

이전, 다음 링크를 연속해서 타고 가는 방식으로 구현합니다. 

cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.

이 조건 덕에 시간 초과는 고려하지 않아도 됩니다.

 

2) C 연산

되돌리기 연산을 고려하여 삭제된 노드들을 그대로 가지고 있는 스택을 만들어줍시다.

일반적인 링크드 리스트의 삭제처럼 구현하고, 스택에 삭제된 노드를 보관합니다.

 

3) Z 연산

삭제한 노드는 링크를 그대로 갖고 있으므로 그냥 복원시키고, 그 노드가 가리키는 두 노드의 링크를 복원할 노드로 이어주면 됩니다.

 

그림으로 설명해보려 했는데 너무 못 그려서 그냥 지웠습니다. 조금 슬프네요..

---

링크드 리스트 외에 다른 풀이가 하나 더 있습니다. 세그먼트 트리를 이용하면 됩니다.

배열로 노드를 관리합니다. 노드가 아직 살아있으면 1, 삭제됐으면 0으로 둡니다. 이 경우 C, Z 연산은 간단히 배열을 수정하는 방법으로 구현할 수 있습니다.

U, D 연산은 세그먼트 트리로 k번째 원소를 구하는 테크닉과 비슷한 메커니즘으로 구현할 수 있습니다.

 

근데 코딩 테스트에서 꼭 이렇게까지 해야 할까요..?

 

 

정답 코드

function solution(n, k, commands) {
    const table = Array(n).fill().map((_, num) => ({
        num,
    }));
    table.forEach((node, i, table) => {
        if (i > 0) node.l = table[i - 1];
        if (i < n - 1) node.r = table[i + 1];
    });
    table.removeHistory = [];
    table.cur = k;
    table.get = function (index) {
        return this[index];
    };
    table.set = function (index, value) {
        this[index] = value;
    };
    table.up = function (num) {
        let node = this.get(this.cur);
        while (num--) {
            node = node.l;
        }
        this.cur = node.num;
    };
    table.down = function (num) {
        let node = this.get(this.cur);
        while (num--) {
            node = node.r
        }
        this.cur = node.num;
    };
    table.remove = function () {
        const now = this.get(this.cur);
        const {l, r} = now;

        this.removeHistory.push(now);
        if (l) l.r = r;
        if (r) r.l = l;
        this.set(this.cur, null);

        if (now.r) this.cur = now.r.num;
        else this.cur = now.l.num;
    };
    table.undo = function () {
        const now = this.removeHistory.pop();
        const {l, r} = now;

        this.set(now.num, now);
        if (l) l.r = now;
        if (r) r.l = now;
    };

    commands.forEach(cmd => {
        const [c, num] = cmd.split(' ');

        if (c === 'U') table.up(+num);
        else if (c === 'D') table.down(+num);
        else if (c === 'C') table.remove();
        else table.undo();
    });

    return table.reduce((ans, cell) => ans += (cell ? 'O' : 'X'), '');
}