programmers Level 3 표 편집

문제

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

걸린 시간

- 실패

풀이

JavaScript

function solution(n, k, cmd) {
    class Node {
        constructor(data) {
            this.prev = null;
            this.data = data;
            this.next = null;
        }
    }
    class DoubleLinkedList {
        constructor() {
            this.head = null;
            this.tail = null;
            this.cur = null;
            this.remove = [];
        }
        init(){
            for(let i = 0; i < n; i++){
                this.insertLast(i);
            }
            if(!this.cur) this.cur = this.head;
        }
        insertLast(data) {
            let node = new Node(data);
            if(!this.head){
                this.head = node;
                this.tail = node;
            }
            else{
                this.tail.next = node;
                node.prev = this.tail;
                this.tail = node;
            }
        }
        UD(X) {
            if(X > 0) this.cur = this.cur.next;
            else this.cur = this.cur.prev;
        }
        C() {
            if(this.cur === this.head){
                this.head = this.cur.next;
                this.remove.push(this.cur);
                this.cur = this.head;
            }
            else if(this.cur === this.tail){
                this.tail = this.cur.prev;
                this.remove.push(this.cur);
                this.tail.next = null;
                this.cur = this.tail;
            }
            else{
                this.cur.prev.next = this.cur.next;
                this.cur.next.prev = this.cur.prev;
                this.remove.push(this.cur);
                this.cur = this.cur.next;
            }
        }
        Z() {
            let node = this.remove.pop();
            if(node.next === this.head){
                this.head.prev = node;
                this.head = node;
            }
            else if(node.prev === this.tail){
                this.tail.next = node;
                this.tail = node;
            }
            else{
                node.prev.next = node;
                node.next.prev = node;
            }
        }
        allData() {
            let current = this.head;
            const ret = [];
            while(current){
                ret.push(current.data);
                current = current.next;
            }
            return ret;
        }
    }
    const dll = new DoubleLinkedList();
    dll.init();
    for(let i = 0; i < k; i++){
        dll.UD(1);
    }
    for(let c of cmd){
        let tmp = c.split(' ');
        let X = parseInt(tmp[1]);
        switch(tmp[0]){
            case 'U':
                for(let i = 0; i < X; i++){
                    dll.UD(-1);
                }
                break;
            case 'D':
                for(let i = 0; i < X; i++){
                    dll.UD(1);
                }
                break;
            case 'C':
                dll.C();
                break;
            case 'Z':
                dll.Z();
                break;
        }
    }
    let arr = Array(n).fill('X');
    for(let i of dll.allData()){
        arr[parseInt(i)] = 'O';
    }
    let answer = arr.join('');
    return answer;
}

행은 가장 최근에 삭제된 순서대로 복구되기 때문에 연결 리스트로 구현하고 삭제 정보를 스택에 담아두면 O(1) 만에 복구가 가능하다. (는 걸 몰라서 한참을 고민했다.)

세그먼트 트리를 이용한 다른 풀이 방법을 생각해내긴 했는데 정의만 알고 구현할 줄을 몰라 풀지 못했다.