문제 링크

프로그래머스 문제

풀이

for문을 반복사용하여 구현을 하려 했지만, 결국 시간초과로 인해서 실패하게된 문제 입니다.
연결리스트를 이용한 풀이 를 참고하여 주석을 달면서 풀이를 진행했습니다.

코드

function solution(n, k, cmd) {
    let answer = new Array(n);
    for(let i = 0; i < n; i++){
        answer[i] = '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;
        }
    }
    
    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':
                // 하나씩 넘기면서 만들어가는 것이 아닌, curNode를 .next를 통해 빠르게 이동시킨다. 
                while(i < count && curNode.next){
                    curNode = curNode.next;
                    i++;
                }
                break;
            case 'C':
                // 여기서 node간 연결관계를 만들어준다. 
                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':
                // 연결관계가 제거된 채로 node가 만들어져 prev와 next가 동시에 없는 경우에 대해서 문제가 있으리라 생각했으나
                // 애초에 'C'를 통해 제거를 진행하면서, 연결관계를 항상 만들어주기 때문에, 연결관계가 완전히 제거된 node는 불가능하다.
                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('');
}

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