[프로그래머스] 표 편집 (JS) - 연결리스트

문제

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

프로그래머스

코드

배열 풀이(시간초과)

function solution(n, k, cmd) {
    const table=[];
    const stack=[];
    let answer="";
    for(let i=0; i<n; i++){
        table.push(i);
    }
    
    for(c of cmd){
        doIt(c);
    }
    
    let idx=0;
    for(let i=0; i<n; i++){
        if(i===table[idx]){
            answer+="O";
            idx++;
        }else answer+="X";
    }
    
    function doIt(c){
        switch(c[0]){
            case 'D':
                const dn = Number(c.substring(2));
                k+=dn;
                break;
            case 'U':
                const un = Number(c.substring(2));
                k-=un;
                break;
            case 'C':
                const item=table.splice(k,1)[0];
                stack.push([k,item]);
                if(k===table.length) k-=1;
                break;
            case 'Z':
                const a=stack.pop();
                table.splice(a[0],0,a[1]);
                if(k>=a[0]) k+=1;
                break;
            default:
                throw new Error('not proper command type');
        }  
    }
    
    return answer;
}

 

연결 리스트 풀이

class Node{
    constructor(val,prev,next){
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}

function solution(n, k, cmd) {
    const answer = Array.from({length:n}, ()=>"O");
    const node = Array.from({length:n}, (_, idx) => new Node(idx, idx-1<0?null:idx-1, idx+1>=n?null:idx+1));
    const stack = [];
    
    for(c of cmd){
        const splited = c.split(" ");
        command=splited[0];
        let num = Number(splited[1]);
        
        switch(command){
            case "U":{
                while(num--){
                    k = node[k].prev;
                }
                break;
            }
            case "D":{
                while(num--){
                    k = node[k].next;
                }
                break;
            }
            case "C":{
                const {prev, next} = node[k];   
                stack.push(node[k]);
                if(node[prev]) node[prev].next = next;
                if(node[next]) node[next].prev = prev;
                
                k = next ? next : prev;
                break;
            }
            case "Z":{
                const popStack = stack.pop();
                const {val, prev, next} = popStack;
                
                if(node[prev]) node[prev].next = val;
                if(node[next]) node[next].prev = val;
                break;
            }
        }
    }
    
    for(s of stack){        
        answer[s.val] = "X";
    }
    
    return answer.join("");
}

정리

연결리스트 vs 배열 (시간복잡도)

연결리스트

- 동적 자료구조

- 연속된 메모리 주소를 할당 받지 않음

- 추가, 삭제 용이

- 데이터 탐색 : O(n)

- 데이터 추가,삭제 : 추가 또는 삭제하려고 하는 데이터가 맨 앞이면 O(1), 그 이후면 O(n)

 

배열

- 정적 자료구조

- 연속된 메모리 주소를 할당 받음

- 접근, 탐색 용이

- 데이터 탐색 : O(1)

- 데이터 추가,삭제 : 추가 또는 삭제하려고 하는 데이터가 맨  뒤이면 O(1), 맨 뒤가 아니라면 O(n)

 

데이터의 접근, 탐색이 중요하면 배열

데이터의 추가, 삭제가 중요하면 연결리스트

 

참조

https://eunchanee.tistory.com/675

https://juyami.tistory.com/102

https://blacklobster.tistory.com/8