[Lv.3!] 표 편집 - 자바

효율성 0점 코드

import java.util.Stack;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        boolean[] isDeleted=new boolean[n];
        Stack<Integer> deleteStack=new Stack<>();
        for (String command : cmd) {
            char c = command.charAt(0);
            if(c=='U'){
                int count=Integer.parseInt(command.split(" ")[1]);
                int step=0;
                while (true){
                    if(isDeleted[--k])
                        continue;
                    step++;
                    if(step==count)
                        break;
                }
            }else if(c=='D'){
                int count=Integer.parseInt(command.split(" ")[1]);
                int step=0;
                while (true){
                    if(isDeleted[++k])
                        continue;
                    step++;
                    if(step==count)
                        break;
                }
            }else if(c=='C'){
                int idx=-1;
                for (int i = k+1; i < n; i++) {
                    if(!isDeleted[i]){
                        idx=i;
                        break;
                    }
                }
                if(idx==-1){
                    //뒤가없다.
                    for(int i=k-1;i>=0;i--){
                        if(!isDeleted[i]){
                            idx=i;
                            break;
                        }
                    }
                }
                deleteStack.add(k);
                isDeleted[k]=true;
                k=idx;
            }else{
                //Z
                Integer pop = deleteStack.pop();
                isDeleted[pop]=false;
            }
        }
        for (int i = 0; i < n; i++) {
            answer+=isDeleted[i]?"X":"O";
        }
        return answer;
    }

}

처음엔 위처럼 단순히 문제의 조건을 그대로 따라 구현하였다..

코드를 쓰면서도 이러면 시간초과날거같다는 생각을 가지고 쓰긴 했지만, 시도는 해봐야지란 생각으로 제출했더니

역시, 정확성은 100점이지만 효율성이 0점인 코드였다.

 

Up,Down의 경우 삭제,복구 전에 굳이 커서를 이동시킬 필요 없이 둘의 차이를 이용해서 삭제,복구 시 한번만 커서를 옮겨주면 된다고 생각해 코드를 조금 수정하였는데, 마찬가지로 효율성이 0점이 나왔다.

 

누적합, 우선순위 큐, 연결리스트 등등 좀 여러가지 방법으로 시도를 해봤는데 그 중 연결리스트가 가장 맞는 방법이라 생각했었다.

삭제한 것을 복구할 때 가장 최근의 것을 복구하기에 stack에서 최근 삭제된 노드를 꺼내고 해당 노드의 prev와 next를 다시 연결해주기만 하면 문제의 조건을 만족하기에 되게 적합한 방법이라 생각했고 자신있게 제출을했더니, 바로 시간초과가 났다..

 

결국 포기하고 여기블로그를 참고해보니 분명 거의 똑같은 코드를 짰는데 유일하게 하나 다른 부분이 있었다..

 

난 그냥 String에 O,X를 더하는 방식으로 답을 넣었는데, StringBuilder를 사용하셨다..

StringBuilder를 사용하는 이유는 여기블로그를 참고해서 정리해보려 한다.

 

우선, int,char와 같이 String은 원시타입이 아닌 객체이기에 문자를 더하는 연산에서 그냥 띡하고 붙여지는게 아닌 기준 문자열에 새로운 문자를 더하여 새로운 String객체를 생성하고 기존의 객체를 GC에 넣어버리는 것이다.

즉, 아주 많은 문자열 덧셈을 하는 경우 상당량의 메모리를 잡아먹게 된다.

 

이와 반대로, StringBuilder의 경우 문자열 자체가 변경가능하다.

즉, 문자를 더한다고 해서 새로운 문자열을 만들고 기존것을 버리는 과정을 반복할 필요가 없다.

 

.. 즉, 로직에서 걸린 시간이 문제가 되는 것이 아닌 정답을 만들어서 내는 과정에서 시간초과가 발생했던 것이였다..

 

그래도, StringBuilder를 2학년때 이후로 정말 오랜만에 공부하게 되어 의미있는 노가다 였다고 생각한다!

 

정답코드

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Stack;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        Stack<Node> deleteStack=new Stack<>();

        Node[] nodeArr=new Node[n+1];
        nodeArr[0]=new Node();
        for (int i = 1; i < n; i++) {
            nodeArr[i]=new Node();
            nodeArr[i].prev=nodeArr[i-1];
            nodeArr[i-1].next=nodeArr[i];
        }
        int upDownCount=0;
        Node nowNode=nodeArr[k];
        for (String command : cmd) {
            char c = command.charAt(0);
            if(c=='U'){
                upDownCount-=Integer.parseInt(command.split(" ")[1]);
            }else if(c=='D'){
                upDownCount+=Integer.parseInt(command.split(" ")[1]);
            }else if(c=='C'){
                if(upDownCount>0){
                    for (int i = 0; i < upDownCount; i++) {
                        nowNode=nowNode.next;
                    }
                }else if(upDownCount<0){
                    upDownCount*=-1;
                    for (int i = 0; i < upDownCount; i++) {
                        nowNode=nowNode.prev;
                    }
                }
                upDownCount=0;
                nowNode.isDeleted=true;
                deleteStack.add(nowNode);
                if(nowNode.prev!=null){
                    nowNode.prev.next=nowNode.next;
                }
                if(nowNode.next!=null){
                    nowNode.next.prev=nowNode.prev;
                    nowNode=nowNode.next;
                }else{
                    //아래에 노드가 없으면 위 노드로 커서 변경
                    nowNode=nowNode.prev;
                }

            }else{
                if(upDownCount>0){
                    for (int i = 0; i < upDownCount; i++) {
                        nowNode=nowNode.next;
                    }
                }else if(upDownCount<0){
                    upDownCount*=-1;
                    for (int i = 0; i < upDownCount; i++) {
                        nowNode=nowNode.prev;
                    }
                }
                upDownCount=0;
                Node pop = deleteStack.pop();
                pop.isDeleted=false;
                if(pop.prev!=null){
                    pop.prev.next=pop;
                }
                if(pop.next!=null)
                    pop.next.prev=pop;
            }
        }
//        for (int i = 0; i < n; i++) {
//            answer+=nodeArr[i].isDeleted?"X":"O";
//        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++){
            if(nodeArr[i].isDeleted) sb.append('X');
            else sb.append('O');
        }

        return sb.toString();
    }
    class Node{
        Node prev;
        Node next;
        boolean isDeleted;
    }

}