프로그래머스: 표 편집 - javascript(양방향 연결리스트)

문제 풀이 출처 

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

프로그래머스

 

문제 풀이 힌트 

양방향 연결 리스트 를 활용한다. 

연결리스트를 모른다면 아래 영상을 가볍게 시청하고 오면 코드가 쉽게 읽힌다. (나도 그랬다..)

https://www.youtube.com/watch?v=K1PlysPgNZY

연결리스트

큰 틀은 이렇다. 

01. 객체를 생성하는 생성자 함수를 정의한다.  

02. 생성자 함수를 활용해서 주어진 n만큼의 node들을 만든다. 

  - 이때, 연결을 해준다. (prev, node 활용)

03. 이동하는 함수 생성 (U, D일 때), 삭제하는 함수 생성(C일때), 복구하는 함수 생성(Z일때) 

04. 문제에서 주어진 cmd를 반복문 돌린다. 그에 맞는 함수(이동, 삭제, 복구 중 하나)를 실행한다. 

05. 모든 반복문이 끝났을 때의 결과를 출력한다. (trashBin이라는 배열에 있는 node 는 'X'로 출력할 것임.)

 

자세한건 코드로 살펴보자! 

이번엔 코드를 나눠서 설명하고, 한꺼번에 모은 코드는 맨 나중에 보여주려 한다. 

왜냐하면 내 블로그까지 왔다면 이전 블로그들에서도 이해가 안돼서 왔을 것이라서,, ! 

아주 ~ 한줄 한줄 설명할 예정 

정답 풀이 코드 

 //01. 객체를 만드는 생성자 함수 정의  
 const Node = function(index, prev){
       this.index = index; //현재 index 저장 
       this.prev =  prev;  //현재 node의 이전 node 저장 
       this.next = null;   //현재 node의 다음 node 저장 
   }
   
   
   let prevNode = new Node(0) //생성자 함수로 index가 0인 객체를 생성. 이것을 prevNode로 설정한다. (그 이유는 다음 코드에서 알 수 있음.)
   let select; //문제에서 "선택된 행" 즉, 현재 선택된 노드를 의미.

 

//02. 생성자 함수를 활용해서 주어진 n만큼의 node들을 만든다. 
//  - 이때, 연결을 해준다. (prev, node 활용)

for(let i=1; i<n; i++){ //아까 index 0의 객체는 미리 생성해줬음. 
       let curNode = new Node(i, prevNode); //현재 i에 맞게 객체 node를 생성한다. (아까 0으로 만든 객체를 prevNode로 할당했으니, 1의 prev가 된다.)
       prevNode.next = curNode; //이전 node의 next는 현재 node가 된다. 
       prevNode = curNode;  //현재 node를 이전의 node로 할당해준다. (다음 i의 node의 prev로 할당하기 위함.)
        
        if(i === k){ //문제에서 주어진 선택된 행 k 와 i가 같아질 때, 
            select = curNode; //현재 객체 node를 선택된 행에 할당한다.  
        }
    }

 

//03. 이동하는 함수 생성 (U, D일 때), 삭제하는 함수 생성(C일때), 복구하는 함수 생성(Z일때) 

let trashBin = []; //삭제되는 node를 넣는 쓰레기통 배열 !!! 
    
    //이동하는 함수 생성 (U, D일 때)
    const moveSelectedNode = (index, direction) => {//index: 몇번 이동, direction:"prev"이거나 "next" 
        for(let i=0; i<index; i++){ //index만큼 이동 
            if(!select[direction]) break; //만약 이동할 node가 더이상 없다면 break; 
            select = select[direction]; //이동하기 ex) 선택 node = 현재 선택 node["prev"]
        }
    }
    
    //삭제하는 함수 생성(C일때)
    const deleteNode = () => {
        const prev = select.prev; //현재 선택 node의 이전 node
        const next = select.next; //현재 선택 node의 이후 node
        
        trashBin.push(select); //현재 선택 node 쓰레기통으로 
        
        select = next ? next : prev; //만약 현재 선택 node의 next가 없으면 select에 prev node를 할당 
        
        //삭제된 현재 노드와의 연결을 끊고, 이전 노드와 이후 노드를 연결하는 작업
        if(prev) prev.next = next; //이전 node의 next는 이제 현재 node가 아니라 현재 node의 이후 node임. 
        if(next) next.prev = prev; //이후 node의 prev는 이제 현재 node가 아니라 현재 node의 이전 node임. 
        
    }
    
    //복구하는 함수 생성(Z일때) 
    const recoverNode = () => {
        const targetNode = trashBin.pop(); //쓰레기통의 마지막꺼 빼자. 
        
        const prev = targetNode.prev; 
        const next = targetNode.next; 
        
        //복구한 node를 다시 연결해주는 작업. 
        if(prev) prev.next = targetNode; 
        if(next) next.prev = targetNode; 
    }

 

 

//04. 문제에서 주어진 cmd를 반복문 돌린다. 그에 맞는 함수(이동, 삭제, 복구 중 하나)를 실행한다.   
  
  cmd.forEach((c) => {
        switch(c[0]){
            case "U":
                moveSelectedNode(c.split(" ")[1], "prev"); 
                break; 
            case "D":
                moveSelectedNode(c.split(" ")[1], "next"); 
                break; 
            case "C":
                deleteNode(); 
                break; 
            case "Z":
                recoverNode(); 
                break;     
        }
    })

 

 

//05. 모든 반복문이 끝났을 때의 결과를 출력한다. (trashBin이라는 배열에 있는 node 는 'X'로 출력할 것임.)

 let answer = new Array(n).fill('O'); //먼저 'O'로 채운 배열 생성
    trashBin.forEach((node) => { //쓰레기통에 있는 Node의 index에 해당하는 배열은 'X'로 할당
        answer[node.index] = 'X'; 
    })
    return answer.join(''); //배열을 문자열로 변환

Only 풀이 코드 

function solution(n, k, cmd) {
     const Node = function(index, prev){
       this.index = index; 
       this.prev =  prev; 
       this.next = null; 
   }
   let prevNode = new Node(0)
   let select; 

    for(let i=1; i<n; i++){
       let curNode = new Node(i, prevNode); 
       prevNode.next = curNode; 
       prevNode = curNode; 
        
        if(i === k){
            select = curNode; 
        }
    }
    
    let trashBin = []; 
    
    const moveSelectedNode = (index, direction) => {
        for(let i=0; i<index; i++){
            if(!select[direction]) break; 
            select = select[direction]; 
        }
    }
    
    const deleteNode = () => {
        const prev = select.prev; 
        const next = select.next; 
        
        trashBin.push(select); 
        
        select = next ? next : prev; 
        
        if(prev) prev.next = next; 
        if(next) next.prev = prev; 
        
    }
    
    const recoverNode = () => {
        const targetNode = trashBin.pop(); 
        
        const prev = targetNode.prev; 
        const next = targetNode.next; 
        
        if(prev) prev.next = targetNode; 
        if(next) next.prev = targetNode; 
    }
    
    cmd.forEach((c) => {
        switch(c[0]){
            case "U":
                moveSelectedNode(c.split(" ")[1], "prev"); 
                break; 
            case "D":
                moveSelectedNode(c.split(" ")[1], "next"); 
                break; 
            case "C":
                deleteNode(); 
                break; 
            case "Z":
                recoverNode(); 
                break;     
        }
    })
    let answer = new Array(n).fill('O'); 
    trashBin.forEach((node) => {
        answer[node.index] = 'X'; 
    })
    return answer.join(''); 
}