Programmers - 표 편집

문제 링크

2021 카카오 채용연계형 인턴십 문제 중 LV.3 표 편집 문제를 풀며 해결한 방법을 풀이하겠습니다.

해당 문제를 고민하다가 풀지 못해서 힌트를 참고해서 제 것으로 만들기 위해 노력했습니다.

해결하지 못한 근본적인 이유는
1. n의 범위 : 5 ≤ n ≤ 1,000,000 에 대해서 ArrayList나 LinkedList를 이용해서 remove연산을 할 경우 시간을 초과하는 현상이 있습니다.
2. 삭제 연산에 대해 Stack 자료 구조를 활용해야 하는 것은 떠올렸습니다. 문제는 해당 위치를 기억할 수 있지만 Insert 연산을 위해 컬렉션을 이용한다면, 최악의 경우 시간 복잡도가 O(n) 만큼 발생합니다.

카카오에서 제공하는 근본적인 풀이

해설링크

LinkedList 자료구조를 구현할 수 있는지가 핵심 이라고 할 수 있습니다.
Node의 prev Node, next Node를 활용하면 되고
복구 연산을 할 경우에도 가장 마지막에 삭제된 노드가 복구되므로, 삭제된 노드의 이전 노드와 다음 노드의 연결을 다시 재구성해주면 됩니다.

O, X 출력을 위한 방법

현재 Node를 이용해 최상단 노드로 이동해서
startIndex부터 현재 노드의 value와 맞는지 비교 연산을 수행하며 출력하면 됩니다.

import java.util.*;

class Node {
    Node prev = null;
    int index;
    Node next = null;

    public Node(int index) {
        this.index = index;
    }
}

class Solution {
    private static Node currentNode;
    private static Map<Integer, Node> map = new HashMap<>();
    private static Stack<Node> stack = new Stack<>();

    public String solution(int n, int k, String[] cmd) {
        StringBuilder sb = new StringBuilder();
        init(n);
        currentNode = map.get(k);

        for(String order : cmd) {
            String[] arr = order.split(" ");

            if(arr[0].equals("U")) {
                selectUp(Integer.parseInt(arr[1]));
            } else if(arr[0].equals("D")) {
                selectDown(Integer.parseInt(arr[1]));
            } else if(arr[0].equals("C")) {
                delete();
            } else if(arr[0].equals("Z")) {
                restore();
            }
        }
        
        while(currentNode.prev != null) { // 최상단 노드로 이동하기
            currentNode = currentNode.prev;
        }
        
        int startIndex = 0;
        
        while(startIndex < n) { // 출력 연산을 위한 동작
            if(startIndex == currentNode.index) {
                sb.append("O");
                startIndex++;
                if(currentNode.next != null) {
                    currentNode = currentNode.next;
                }
            } else if(startIndex != currentNode.index) {
                sb.append("X");
                startIndex++;
            }
        }
        
        return sb.toString();
    }

    private static void init(int n) {
        Node prev = null;
        Node node = null;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                node = new Node(i);
                prev = node;
            } else if (i == n) {
                node = new Node(i);
                prev.next = node;
                node.prev = prev;
            } else {
                node = new Node(i);
                prev.next = node;
                node.prev = prev;
                prev = node;
            }
            map.put(i, node);
        }
    }

    private static void selectUp(int number) {
        for(int i = 0; i < number; i++) {
            currentNode = currentNode.prev;
        }
    }

    private static void selectDown(int number) {
        for(int i = 0; i < number; i++) {
            currentNode = currentNode.next;
        }
    }

    private static void delete() {
        // 스택에 담기
        stack.push(currentNode);
        
        if(currentNode.prev == null) { // 맨 위 노드인 경우
            currentNode = currentNode.next;
            currentNode.prev = null;
        } else if(currentNode.next == null) { // 맨 아래 노드인 경우
            currentNode = currentNode.prev;
            currentNode.next = null;
        } else { // 나머지
            Node prev = currentNode.prev;
            Node next = currentNode.next;
            prev.next = next;
            next.prev = prev;
            currentNode = currentNode.next;
        }
    }

    private static void restore() {
        Node back = stack.pop(); // 삭제된 노드 불러오기
        Node next = back.next;
        Node prev = back.prev;
        
        if(next != null) { // 삭제된 노드의 다음이 null이 아니라면
            next.prev = back;
        }
        
        if(prev != null) { // 삭제된 노드의 이전이 null이 아니라면
            prev.next = back;
        }
    }
}