2021 Kakao internship - 표 편집(링크드리스트, 이진트리) java 풀이

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

- 제한조건을 유심히 보고 구현해야 될 문제이다. 행의 갯수가 최대 100만이기 때문에 만약 인덱스 0번 row와 '100만'번 row 사이를 이동하는 케이스라면 cmd의 갯수 20만 * 100만번을 이동해야될 수 있다. 그런데 up, down 연산시 나오는 행 이동 X의 총 합이 최대 100만이므로 삭제된 행들을 띄어넘을 수 있는 자료구조나 알고리즘을 사용하면 이 연산을 O(20만 + 100만)으로 줄일 수 있다. 

- 행이 삭제 되었을 때, 그 행을 저장할 스택과 해당 행의 이전, 이후 행의 주소값, 인덱스값 을 저장하기 위해서 양방향 링크드리스트를 직접 구현하였다. C++이라면 list 컨테이너가 양방향 링크드리스트로 구현되어 있으므로 그걸 사용해도 될 것 같다. 

- 양방향 리스트 구현 관련한 개념을 정리한 포스트를 작성해 두었다. (https://ellerymoon.tistory.com/108)

https://sebhastian.com/doubly-linked-list-javascript/

- 행 삭제와 복구 로직이 살짝 햇깔렸다. 특히 커서가 가리키는 행이 head, tail인 경우의 예외처리를 하는 데에 시간이 많이 소요됬는데, 만약 java 언어로 링크드리스트를 직접 구현해보았다면 prev, next 연결을 하는 게 좀 더 수월했을 것 같다. 

- 삭제된 행을 뛰어넘는 연산이 필요하므로 링크드리스트를 이용하였는데, 세그먼트 트리를 이용해서도 (logN)^2 이내로 풀 수 있다고 한다. 세그먼트트리도 시간여유가 되면 학습해야겠다고 생각했다. 

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        Node head = null;
        Node tail = null;
        Node cursor = null;
        Stack<Node> st = new Stack<>();

        for (int i = 0; i < n; ++i) {
            if (head == null) {
                head = new Node(i, null, null);
                tail = head;
            } else {
                tail.next = new Node(i, tail, null);
                tail = tail.next;
            }
            if (i == k) cursor = tail;
        }

        for (String c : cmd) {
            char ch = c.charAt(0);

            if (ch == 'U' || ch == 'D') {
                int jump = Integer.parseInt(c.substring(2));

                if (ch == 'U') {
                    while (jump-- > 0 && cursor.prev != null) {
                        cursor = cursor.prev;
                    }
                } else if (ch == 'D') {
                    while (jump-- > 0 && cursor.next != null) {
                        cursor = cursor.next;
                    }
                }
            } else if (ch == 'C') { // 선택행 삭제, 바로 아래행 선택, 삭제된 행이 tail이면 윗행 선택
                st.push(cursor);
                if (tail == cursor) { // tail이면
                    tail = tail.prev;
                    tail.next = null;
                    cursor = tail;
                } else { // tail 아니면
                    if (cursor.prev != null) cursor.prev.next = cursor.next;
                    cursor.next.prev = cursor.prev;
                    cursor = cursor.next;
                }
            } else if (ch == 'Z') { // 가장 최근 삭제행 복구
                Node node = st.pop();

                if (node.prev != null) node.prev.next = node;
                else head = node;

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

        StringBuilder sb = new StringBuilder("O".repeat(n));
        while (!st.isEmpty()) {
            Node cur = st.pop();
            sb.setCharAt(cur.idx, 'X');
        }

        return sb.toString();
    }

    class Node {
        int idx;
        Node prev;
        Node next;

        Node(int idx, Node prev, Node next) {
            this.idx = idx;
            this.prev = prev;
            this.next = next;
        }
    }
}