[JS/Programmers] 81303. 표 편집

💬 문제

문제 난이도: Programmers Lv.3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/81303

❗️접근방법

링크드 리스트

👆 1차 코드(통과❌)

function solution(n, k, cmd) {
    const arr = new Array(n).fill('O');
    const stack = [];
    let cur = k;
    for (let i = 0 ; i < cmd.length; i+= 1){
        const elem = cmd[i].split(' ');
        let num = 0;
        switch(elem[0]){
            case 'D':
                num = parseInt(elem[1]);
                while (num > 0){
                    cur += 1;
                    if (arr[cur] === 'O') num -= 1;
                    else continue;
                }
                break;
            case 'U':
                num = parseInt(elem[1]);
                while (num > 0){
                    cur -= 1;
                    if (arr[cur] === 'O') num -= 1;
                    else continue;
                }
                break;
            case 'C':
                stack.push(cur);
                arr[cur] = 'X';
                cur += 1;
                if (cur === n){
                    cur -= 2;
                    while (arr[cur] === 'X'){
                        cur -=1;
                    }
                }else{
                    while(arr[cur] === 'X'){
                        cur += 1;
                    }
                }
                break;
            case 'Z':
                const re = stack.pop();
                arr[re] = 'O';
                break;
        }
        
    }
    return arr.join('');
    
}

시간초과 원인
OXXXXXO일 경우에 X를 모두 거치며 O을 찾아야 하므로 시간 초과 발생.

✌️ 2차 코드(통과❌)

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

function solution(n, k, cmd) {
    const arr = new Array(n).fill('O');
    let prevNode = new Node(0);
    let select;
    
    for (let i = 1; i < n; i+=1){
        const curNode = new Node(i, prevNode);
        prevNode.next = curNode;
        prevNode = curNode;
        if(i === k){
            select = curNode;
        }
    }
    const bin = [];
    for (let i = 0; i < cmd.length; i+=1){
        const elem = cmd[i].split(' ');
        let num;
        
        switch(elem[0]){
            case 'D':
                num = parseInt(elem[1]);
                while(num > 0){
                    select = select.next;
                    num -=1;
                }
                break;
            case "U":
                num = parseInt(elem[1]);
                while(num > 0){
                    select = select.prev;
                    num -=1;
                }
                break;
            case 'C':
                arr[select.index] = 'X';
                bin.push(select);
                if (select.next === null){
                    select.prev.nexte = null;
                    select = select.prev;
                }else{
                    select.prev.next = select.next; // ---1️⃣
                    select.next.prev = select.prev;
                    select = select.next;
                }
                break;
            case 'Z':
                const node = bin.pop();
                arr[node.index] = 'O'
                const p = node.prev;
                const n = node.next;
                if(p) p.next = node;
                if(n) n.prev = node;
                break;
        }
    }
    return arr.join('');

}

런타임 에러
select.prev가 null이면 select.prev.next는 null.next을 의미하므로 error가 발생한다.

링크드 리스트
1차 풀이에서 C 명령어로 인해 행이 삭제되어도 그대로 둔 이유는 배열의 원소 삭제 및 추가는 O(N) 만큼의 시간이 걸리기 때문이었다.
하지만 배열로 이 문제를 풀면 1차 풀이처럼 시간 초과가 발생한다.
그렇다면 원소의 삭제 및 추가가 O(1) 만큼의 시간이 드는 링크드 리스트를 사용하면 된다.
노드는 인덱스와 자신의 왼쪽(앞), 오른쪽(뒤)에 오는 노드를 멤버로 가지고 있다.

🤟 3차 코드(통과✅)

const Node = function (index){
    this.index = index;
    this.prev = null;
    this.next = null;
}

function solution(n, k, cmd) {
    const answer = new Array(n).fill('O');
    let prevNode = new Node(0);
    let select = prevNode;
    
    for (let i = 1; i < n; i+=1){
        const curNode = new Node(i);
        prevNode.next = curNode;
        curNode.prev = prevNode;
        prevNode = curNode;
        if(i === k){
            select = curNode;
        }
    }
    const bin = [];
    for (let i = 0; i < cmd.length; i+=1){
        const elem = cmd[i].split(' ');
        let num;
        
        switch(elem[0]){
            case 'D':
                num = parseInt(elem[1]);
                while(num > 0){
                    select = select.next;
                    num -=1;
                }
                break;
            case "U":
                num = parseInt(elem[1]);
                while(num > 0){
                    select = select.prev;
                    num -=1;
                }
                break;
            case 'C':
                bin.push(select);
                answer[select.index] = 'X'
                if (select.next === null){
                    select.prev.next = null;
                    select = select.prev;
                }
                else{
                    if(select.prev){
                        select.prev.next = select.next;
                    }
                    select.next.prev = select.prev;
                    select = select.next;
                }
                break;
            case 'Z':
                const node = bin.pop();
                answer[node.index] = 'O'
                const p = node.prev;
                const n = node.next;
                if (p) p.next = node;
                if (n) n.prev = node;
                break;
        }
    }
    return answer.join('');
}