[Javascript/PGS] Lv.3 : 표 편집 (연결리스트)

 

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

프로그래머스

---

프로그래머스 레벨 3. 정답률 40%

 

 

첫 시도에서 Map을 활용하여 풀었다.

그런데 효율성 실패..!ㅠㅠ

단순 구현이 아니라, 연결 리스트 형식으로 풀어야 하는 문제였다 🤯

 

그래서 next, prev 배열에 각각 다음/이전 위치를 저장해주며 연결 관계를 나타냈다.

이건 실제 연결리스트 기법은 아니고, 배열로 작동 방식을 모방한 것이다!

실제로 연결리스트를 사용하려면, 아래와 같이 포인터를 가지는 노드 클래스를 선언하고 쓰면 된다

class Node {
    constructor(index) {
        this.index = index;
        this.prev = null;
        this.next = null;
    }
}

 

인덱스 연결시키느라 머리 터질 뻔 했는데 끈기로 붙잡고 해결 완....🥹

 

 

나의 풀이 (배열 활용)

function solution(n, k, cmd) {
    let nowIdx = k;
    let deleted = [];
    let next = new Array(n).fill().map((_,i)=>i+1);
    let prev = new Array(n).fill().map((_,i)=>i-1); // 첫 인덱스의 prev는 -1
    next[n-1] = -1; // 마지막 인덱스의 next는 -1
    
    cmd.forEach(word=>{
        if(word[0]=='U'){
            let num = word.split(' ')[1];
            // num만큼 prev를 따라 이동
            while(num>0) {
                if(prev[nowIdx]<0) break;
                nowIdx = prev[nowIdx];
                num--;
            }
        }
        if(word[0]=='D'){
            let num = word.split(' ')[1];
            // num만큼 next를 따라 이동
            while(num>0) {
                if(next[nowIdx]<0) break;
                nowIdx = next[nowIdx];
                num--;
            }
        }
        if(word[0]=='C'){
            deleted.push([nowIdx,prev[nowIdx],next[nowIdx]]);
            // 이전값의 next를 현재값 next로, 다음값의 prev를 현재값 prev로 이어줌
            if(prev[nowIdx]!=-1) next[prev[nowIdx]] = next[nowIdx];
            if(next[nowIdx]!=-1) prev[next[nowIdx]] = prev[nowIdx];
            
            nowIdx = next[nowIdx]<0? prev[nowIdx] : next[nowIdx];
        }
        if(word[0]=='Z' && deleted.length>0){
            let [idx,P,N] = deleted.pop();
            if(P!=-1) next[P] = idx;
            if(N!=-1) prev[N] = idx;
        }
    })
    
    const answer = Array(n).fill('O');
    for (let [i,P,N] of deleted) {
        answer[i] = 'X';
    }
    
    return answer.join('');
}