programmers. 표 편집

문제

코딩테스트 연습 - 표 편집

풀이

간단한 구현 문제

어떤 방식으로 구현할 것인지는 사람마다 갈리겠지만 나는 처음에 배열로 구현했다

n크기만큼 배열을 생성한 뒤에 ture로 초기화한다

'C' 명령어가 들어와서 삭제된다면 false로 바꾸고 해당 인덱스를 history라는 스택에 넣고

'Z' 명령어가 들어오면 history 스택에서 pop한 뒤 해당 배열의 인덱스를 true로 바꾼다

하지만 이렇게 배열로 구현하면 현재 선택된 행을 다루는 것에서 문제가 발생한다

O

O

X

O

X

X

X

X

이 상황에서 'C'명령어가 들어온다면 포인터는 1을 가르켜야하는데 예외처리 부분이 복잡해지는 것 + 시간복잡도가 증가하기 때문에 테스트 케이스를 통과하지 못한다

양방향 연결 리스트를 이용해서 문제를 풀면 시간 복잡도 또한 만족시킬 수 있다

코드

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

    const makeTable = number => {
        const root = new Node(0);

        let currentNode = root;

        for(let i = 1;i < number; i++){
            const nextNode = new Node(i, currentNode);
            currentNode.next = nextNode;
            nextNode.prev = currentNode;
            currentNode = nextNode;
        }

        return root;
    };

    const moveCursor = (k, root, direction = 'next') => {
        let currentNode = root;
        for(let i = 0; i < k; i++){
            currentNode = currentNode[direction];
        }
        return currentNode;
    };


    const removeNode = currentNode => {
        const prev = currentNode.prev;
        const next = currentNode.next;

        if(prev){
            prev.next = next;
        }
        if(next){
            next.prev = prev;
        }
    };

    const restore = lastNode => {
        const prev = lastNode.prev;
        const next = lastNode.next;

        if(prev){
            prev.next = lastNode;
        }
        if(next){
            next.prev = lastNode;
        }
    };

    const makeAnswer = (root, answer) => {
        while (root) {
            answer[root.index] = 'O';
            root = root.next;
        }
        return answer.join('');
    };

    const resetRoot = root => {
        while (root.prev){
            root = root.prev;
        }
        return root;
    };

    const solution = (n, k, cmd) => {
        const answer = Array(n).fill().map(()=>'X');
        let root = makeTable(n);
        let currentNode = moveCursor(k, root);
        const history = [];

        const down = number => {
            currentNode = moveCursor(number, currentNode, 'next');
        };

        const up = number => {
            currentNode = moveCursor(number, currentNode, 'prev');
        };

        const remove = () => {
            history.push(currentNode);
            removeNode(currentNode);
            if(root === currentNode){
                root = currentNode.next;
            }
            currentNode = currentNode.next || currentNode.prev;
        };

        const undo = () => {
            const lastNode = history.pop();
            restore(lastNode);
        };

        const executor = {
            U: up,
            D: down,
            C: remove,
            Z: undo
        };

        cmd.forEach(command => {
            const [order, number] = command.split(' ');
            executor[order](number);
        });
        root = resetRoot(root);
        return makeAnswer(root, answer);
    };