[Programmers] 2021 카카오 채용연계형 인턴십 표 편집 - JAVA

문제

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

프로그래머스

 

 

풀이 과정

이 문제는 연결 리스트 문제이다. 처음에는 자바에서 제공해주는 LinkedList로 접근했었는데, 효율성 테스트에서 실패했다.

이 문제는 리스트의 삽입/삭제를 효율적으로 처리할 수 있는 자료구조를 사용해야 한다.

 

왜 자바의 LinkedList는 실패하는 것일까?

기본적으로 연결 구조는 삽입/삭제는 빠르고, 읽는 속도가 느리다.

자바의 LinkedList는 노드 연결 구조를 가진다. 기본적으로 삽입/삭제 연산만을 보면 빠르지만, 삽입/삭제 시 해당 위치까지 이동해야 하므로 최악의 경우 시간복잡도가 O(N) 이다.

그러므로, LinkedList는 remove/add는 시간복잡도가 O(N)이기 때문에 최악의 경우 명령어 최대 200,000개, n이 최대 1,000,000개 이므로 시간초과가 발생한다.

 

문제 접근 방식

이중 연결 리스트 구조를 직접 구현해서 풀어보았다.

자료구조를 직접 구현해보았다면, 해볼만한 문제인 것 같다.

• 각 행을 Node로 표현한다.
• 각 Node는 prev(이전노드), next(다음노드)를 가진다.
• 헤드노드는 prev는 null이고, 꼬리노드는 next가 null이다.
• 그 외의 모든 노드는 prev, next로 연결된 구조이다.
• 이동(U, D)의 경우 연결된 노드를 따라 이동하면 된다.
• 삭제(C)의 경우 이전/다음 노드를 서로 연결 해준다. 삭제된 노드는 복구를 위해 Stack에 저장한다.
• 복구(Z)의 경우 복구할 노드를 Stack에서 꺼낸 다음 해당 노드를 연결해준다.

 

코드

class Solution {

    static class Node {
        Node prev;
        Node next;
        boolean removed;

        // 이전 노드로 이동
        public Node moveUp(int movement) {
            Node temp = this;
            for (int i = 0; i < movement; i++) {
                temp = temp.prev;
            }
            return temp;
        }

        // 다음 노드로 이동
        public Node moveDown(int movement) {
            Node temp = this;
            for (int i = 0; i < movement; i++) {
                temp = temp.next;
            }
            return temp;
        }

        // 삭제(이전, 다음 노드를 서로 연결해준다.)
        public Node remove() {
            // 이전, 다음 노드를 서로 연결해준다.
            this.removed = true;

            // 헤드 노드
            if (this.prev == null) {
                this.next.prev = null;
                return this.next;
            }

            // 꼬리 노드
            if (this.next == null) {
                this.prev.next = null;
                return this.prev;
            }

            this.prev.next = this.next;
            this.next.prev = this.prev;
            return this.next;
        }

        // 복구
        public void reStore() {
            this.removed = false;
            if (this.prev != null) {
                this.prev.next = this;
            }

            if (this.next != null) {
                this.next.prev = this;
            }
        }
    }

    public String solution(int n, int k, String[] cmds) {
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node();
            if (i == 0) {
                continue;
            }
            // 노드 연결
            nodes[i - 1].next = nodes[i];
            nodes[i].prev = nodes[i - 1];
        }

        Stack<Node> history = new Stack<>();
        Node current = nodes[k];
        for (String cmd : cmds) {
            StringTokenizer st = new StringTokenizer(cmd);
            String command = st.nextToken();

            if (command.equals("U")) { // 위로 이동
                int movement = Integer.parseInt(st.nextToken());
                current = current.moveUp(movement);
            } else if (command.equals("D")) { // 아래로 이동
                int movement = Integer.parseInt(st.nextToken());
                current = current.moveDown(movement);
            } else if (command.equals("C")) { // 삭제
                history.push(current);
                current = current.remove();
            } else if (command.equals("Z")) {  // 복구
                Node target = history.pop();
                target.reStore();
            }
        }

        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (nodes[i].removed) {
                answer.append("X");
            } else {
                answer.append("O");
            }
        }
        return answer.toString();
    }
}