Programmers - 표편집 with JAVA (V)

 

 

 

해결

이 문제는 시간복잡도를 고려해야하는 문제이다. ArrayList나 Map 등 다른 것들을 사용해서 해결하려고 했지만 시간복잡도에서 문제가 생겼고 구현하기도 어렵다. LinkedList로 해결을 하였고 코드는 아래와 같다.

 

원리적으로는 저장공간을 늘려 검색이나 삭제등의 복잡도를 줄이는 원리를 통해 시간복잡도를 전체적으로 줄인다.

 

 

코드

import java.util.*;
class Solution {
    static class Node{
        public Node prev;
        public Node next;
        public boolean isDeleted = false;
    }
    public static String solution(int n, int k, String[] cmd) {
        Stack<Node> deleted = new Stack<>();
        Node[] nodes = new Node[n+1];
        nodes[0] = new Node();
        for(int i=1; i<n; i++){
            Node now = new Node();
            nodes[i] = now;
            nodes[i-1].next = now;
            nodes[i].prev = nodes[i-1];
        }
        Node now = nodes[k];
        for(String cm : cmd){
            char what = cm.charAt(0);
            if(what == 'U'){
                int how = Integer.valueOf(cm.substring(2, cm.length()));
                while(how > 0){
                    how -= 1;
                    now = now.prev;
                }
            }
            if(what == 'D'){
                int how = Integer.valueOf(cm.substring(2, cm.length()));
                while(how > 0){
                    how -= 1;
                    now = now.next;
                }
            }
            if(what == 'C'){
                now.isDeleted = true;
                Node prevNode = now.prev;
                Node nextNode = now.next;
                deleted.add(now);
                if(prevNode != null){
                    prevNode.next = nextNode;
                }
                if(nextNode != null){
                    nextNode.prev = prevNode;
                    now = nextNode;
                }
                if(nextNode == null){
                    now = prevNode;
                }
            }
            if(what == 'Z'){
                Node delNode = deleted.pop();
                delNode.isDeleted = false;
                if(delNode.prev != null){
                    delNode.prev.next = delNode;   
                }
                if(delNode.next != null){
                    delNode.next.prev = delNode;   
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            if(nodes[i].isDeleted){
                sb.append("X");
            }
            else{
                sb.append("O");
            }
        }
        return sb.toString();
    }
}

 

 

실수 정리

1. U, D 에서 X는 두자리일 수 있다.

2. C, Z 에서 NullPointException은 (객체 = null)이 아니라 (null = 객체)에서 발생하니 잘 파악하자.

import java.util.*;
class Solution {
    public static class Node{
        public Node before;
        public Node after;
        public int number;
        public boolean isDeleted = false;
        public Node(int number){
            this.number = number;
        }
    }
    public static String solution(int n, int k, String[] cmd) {
        List<Node> check = new ArrayList<>();
        Stack<Node> deleted = new Stack<>();
        check.add(new Node(0));
        for(int i=1; i<n; i++){
            Node now = new Node(i);
            now.before = check.get(check.size()-1);
            check.get(check.size()-1).after = now;
            check.add(now);
        }
        Node node = check.get(k);
        for(String cm : cmd){
            char c = cm.charAt(0);
            if(c == 'U'){
                int count = Integer.valueOf(cm.substring(2, cm.length()));
                for(int i=0; i<count; i++){
                    node = node.before;
                }
            }
            if(c == 'D'){
                int count = Integer.valueOf(cm.substring(2, cm.length()));
                for(int i=0; i<count; i++){
                    node = node.after;
                }
            }
            if(c == 'C'){
                node.isDeleted = true;
                Node before = node.before;
                Node after = node.after;
                deleted.add(node);
                if(before != null){
                    before.after = after;
                }
                if(after != null){
                    after.before = before;
                    node = after;
                }
                if(after == null){
                    node = before;
                }
            }
            if(c == 'Z'){
                Node current = deleted.pop();
                current.isDeleted = false;
                Node before = current.before;
                Node after = current.after;
                if(before != null){
                    before.after = current;   
                }
                if(after != null){
                    after.before = current;   
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(Node now : check){
            if(now.isDeleted){
                sb.append("X");
            }
            else{
                sb.append("O");
            }
        }
        return sb.toString();
    }
}