Programmers - 표 편집

문제 링크

문제를 보고 2가지의 풀이 방법이 떠올랐다.

1. 삭제되지 않은 Row를 List로 관리하는 방법
   • U,D : O(1) (index += X)
   • C,Z : O(N) (List를 다시 만드는 과정)
2. LinkedList처럼 각 Node별 prev,next를 이용하는 방법
   • U,D : O(X) (주어진 X만큼 이동을 반복해야 함)
   • C,Z : O(1) (연결만 제거)

1번 방법으로 풀었을 때는 시간초과가 났고 2번 방법으로 풀었을 때는 통과가 되었다.
하지만 1,2번 모두 최악의 경우에는 시간초과가 발생해야 한다.
출제의도가 LinkedList 였나보다.

import java.util.*;

class Solution {

    Stack<Node> removed = new Stack<>();
    Node[] nodes;
    Node currentNode;

    public String solution(int n, int k, String[] cmd) {
        init(n,k);

        for(int i=0;i<cmd.length;i++){
            if(cmd[i].equals("C")){
                remove();
            }else if(cmd[i].equals("Z")){
                rollback();
            }else{
                String[] splitted = cmd[i].split(" ");
                int x = Integer.parseInt(splitted[1]);
                if(splitted[0].equals("U"))
                    up(x);
                else
                    down(x);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++){
            if(nodes[i].isRemoved)
                sb.append('X');
            else
                sb.append('O');
        }

        return sb.toString();
    }

    private void init(int n, int k){
        nodes = new Node[n];
        nodes[0] = new Node(0);
        for(int i=1;i<n;i++){
            nodes[i] = new Node(i);
            nodes[i].prev = nodes[i-1];
            nodes[i-1].next = nodes[i];
        }
        currentNode = nodes[k];
    }

    private void up(int x){
        for(int i=0;i<x;i++){
            if(currentNode.prev == null)
                break;
            currentNode = currentNode.prev;
        }
    }

    private void down(int x){
        for(int i=0;i<x;i++){
            if(currentNode.next == null)
                break;
            currentNode = currentNode.next;
        }
    }

    private void remove(){
        Node before = currentNode.prev;
        Node next = currentNode.next;
        if(before != null)
            before.next = next;
        if(next != null)
            next.prev = before;

        removed.add(currentNode);
        currentNode.isRemoved = true;

        if(currentNode.next != null)
            currentNode = currentNode.next;
        else
            currentNode = currentNode.prev;
    }

    private void rollback(){
        Node node = removed.pop();
        node.isRemoved = false;
        Node before = node.prev;
        Node next = node.next;

        if(before!= null)
            before.next = node;
        if(next != null)
            next.prev = node;
    }

    static class Node{
        Node prev;
        Node next;
        int value;
        boolean isRemoved;
        public Node(int value) {
            this.value = value;
        }
    }
}