프로그래머스 표 편집 python, java

효율성 테스트가 있는 문제였다.
문제 자체는 간단해 보이는데 시간을 고민해야 했다.

문제는 Linked List 로 풀었는데 솔직히 효율성이 왜 통과됐는지 의문이다.
명령어 개수 20만개, 이동하는 값 x의 최대값이 30만
음.. 최대값으로 이동만하면 Linked List는 당연히 시간초과아닌가..?

📜 문제 바로 가기 : 표 편집

제출코드

파이썬

class Node:
    def __init__(self, value):
        self.up = None
        self.down = None
        self.value = value

class LinkedList:
    def __init__(self, node):
        self.head = node;

        
def solution(n, k, cmd):

    isDelete = [False] * n
    stack = []
    linkedList = LinkedList(Node(0))
    now_node = linkedList.head
    for i in range(1, n):
        node = Node(i)
        now_node.down = node
        node.up = now_node
        now_node = node
    
    now_node = linkedList.head
    for _ in range(k):
        now_node = now_node.down

    
    def down(x): # 선택된 행에서 x칸 밑으로
        nonlocal now_node
        for _ in range(x):
            now_node = now_node.down
        
    def up(x):
        nonlocal now_node
        for _ in range(x):
            now_node = now_node.up
    
    def delete():
        nonlocal now_node
        stack.append(now_node)
        isDelete[now_node.value] = True
        
        upNode = now_node.up
        downNode = now_node.down
        
        if upNode:
            upNode.down = downNode
        if downNode:
            downNode.up = upNode
            now_node = downNode
        else:
            now_node = upNode
            
    def restore():
        nonlocal now_node
        reNode = stack.pop()
        isDelete[reNode.value] = False
        upNode = reNode.up
        downNode = reNode.down
        if upNode:
            upNode.down = reNode
        if downNode:
            downNode.up = reNode
        
    
    for com in cmd:
        if com[0] == "U":
            c, x = com.split()
            up(int(x))
        elif com[0] == "D":
            c, x = com.split()
            down(int(x))
        elif com[0] == "C":
            delete()
        else:
            restore()
    
        
    answer = ""
    for i in isDelete:
        if i == False:
            answer += "O"
        else:
            answer += "X"
            
    return answer

자바

import java.util.Stack;

class Solution {
    
    static MyLL ll = new MyLL(new Node(0));
    static Boolean[] isDelete;
    static Node now;
    static Stack<Node> stack = new Stack<Node>();
    
    public String solution(int n, int k, String[] cmd) {
        
        isDelete = new Boolean[n];
        for (int i=0; i<n; i++) {
            isDelete[i] = false;
        }
        
        now = ll.head;
        for (int i=1; i < n; i++) {
            Node tmp = new Node(i);
            now.down = tmp;
            tmp.up = now;
            now = tmp;
        }
        
        now = ll.head;
        for (int i=0; i<k; i++) {
            now = now.down;
        }
        
        for (String command : cmd) {
            String[] com = command.split("\\s+");
            if (com[0].equals("U")) {
                int x = Integer.parseInt(com[1]);
                up(x);
            } else if (com[0].equals("D")) {
                int x = Integer.parseInt(com[1]);
                down(x);
            } else if (com[0].equals("C")) {
                del();
            } else {
                restore();
            }
        }
        
        
        StringBuilder answer = new StringBuilder();
        for (Boolean flag : isDelete) {
            if (flag == true) {
                answer.append("X");
            } else {
                answer.append("O");
            }
        }
        return answer.toString();
    }
    
    public void up(int x) {
        for (int i=0; i<x; i++) {
            now = now.up;
        }
    }
    
    public void down(int x) {
        for (int i=0; i<x; i++) {
            now = now.down;
        }
    }
    
    public void del() {
        stack.push(now);
        isDelete[now.value] = true;
        
        Node upNode = now.up;
        Node downNode = now.down;
        
        if (upNode != null) {
            upNode.down = downNode;
        }
        if (downNode != null) {
            downNode.up = upNode;
            now = downNode;
        } else {
            now = upNode;
        }
        
    }
    
    public void restore() {
        Node reNode = stack.pop();
        isDelete[reNode.value] = false;
        Node upNode = reNode.up;
        Node downNode = reNode.down;
        
        if (upNode != null) {
            upNode.down = reNode;
        }
        if (downNode != null) {
            downNode.up = reNode;
        }
    }
}

class Node {
    Node up = null;
    Node down = null;
    int value;
    public Node(int value) {
        this.value = value;
    }
}

class MyLL {
    Node head;
    
    public MyLL(Node node) {
        this.head = node;              
    }
}

---

접근방법

"Z" 명령어는 선택된 행이 변하지 않아서 상관이 없는데 "C" 명령어는 변하기 때문에 고려를 해줘야 한다.

• 삭제된 행 아래에 데이터가 있는 경우
  데이터 삭제로 아래있는 행이 올라옴으로 선택된 행은 아래있는 데이터가 된다.

• 삭제된 행 아래에 데이터가 없는 경우
  올라올 행이 없으므로 선택된 행이 위에 있는 데이터로 간다.

StringBuilder

자바로 제출할때 StringBuilder를 모르고 계속 + 연산자로 answer에 O, X 를 붙였다.
당연히 효율성 테스트에서 시간초과가 나왔고 분명 파이썬이랑 같은 로직인데 왜 그런거지하며 한참을 고민했다.
결론은 Java에서 문자열 연산이 많을 때는 StringBuilder를 활용하자!

String, Stringbuilder, StringBuffer 차이 구분하기