2021 카카오 채용연계형 인턴십 Lv3 표 편집 [Java]

2021 카카오 채용연계형 인턴십 Lv3 표 편집

1. 문제 링크

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

2. 문제 해설

배열의 경우 삽입, 삭제의 시간복잡도가 O(n), 연결리스트의 경우 O(1)이다. 삽입, 삭제가 빈번하게 이뤄지는 경우 연결리스트를 이용하는 것이 효율적이다. 이 문제의 경우 행의 최대 갯수도 100만이고 명령의 갯수도 최대 20만이기에 이므로 연결리스트를 이용하여 푸는 것이 좋다고 생각했다.

행들의 정보를 담기 위해 Node 클래스를 만들었다. Node 클래스에는 이전 노드를 가리키는 prev, 다음 노드를 가리키는 next, 삭제 여부를 담는 removed가 있다. 각 행들은 Node 클래스를 이용하여 표현했고, 행들을 담아줄 Node 배열을 만들었다. 13~22번째 줄 코드에서 Node 배열을 초기화해주고 양방향 연결리스트처럼 이어주었다.

이제 각 명령어 별로 어떻게 구현을 할 것인지 한번 살펴보자. 일단 그 전에 현재 선택된 행을 나타내는 Node cur를 만들어줬다.

1) "U X"
X칸 만큼 cur의 prev로 이동하여 cur를 업데이트 해준다.

2) "D X"
X칸 만큼 cur의 next로 이동하여 cur를 업데이트 해준다.

3) "C"
삭제될 행을 스택에 담아줄 것이다. 이유는 뒤에 나올 "Z" 명령어에서 가장 최근에 삭제된 행을 복구해야하는데 스택을 사용하면 쉽게 처리할 수 있기 때문이다. 스택에 담아준 후, 삭제될 행의 removed를 true로 바꿔준다. 그리고 삭제된 행의 위 아래 행을 가리키는 변수를 각각 up, down이라고 해보자. 현재 행이 삭제되었으므로 up.next = down, down.prev = up 처리를 해주면 된다. 다만, 삭제된 행이 맨 첫번째 행이거나 맨 마지막 행이라면 up이나 down에 null 값이 들어있어 오류가 발생할 것이다. 그러므로 그에 관한 예외 처리를 해줘야한다.
그리고 삭제된 행이 마지막 행이 아니라면 down를 선택해주고, 마지막 행이면 up을 선택해주면 된다.

4) "Z"
가장 최근에 삭제된 행을 다시 복구해보자. 스택의 맨 위에 담겨있는 행이 가장 최근에 삭제된 행이므로 스택 맨 위의 원소를 가져와주고 reNode라고 명명하자. 그리고 reNode의 removed를 false로 바꿔준다. reNode는 삭제되기 전의 본인 위 아래 행들의 정보를 담고 있다. 그것들을 각각 up, down이라고 해보자. reNode를 다시 복구할 것이므로 up.next = reNode, down.prev = reNode 처리를 해주면 된다. 다만, 복구될 행이 맨 첫번째 행이거나 맨 마지막 행이라면 up이나 down에 null 값이 들어있어 오류가 발생할 것이므로 그에 관한 예외 처리를 해주고 처리해준다.

명령어에 관한 처리를 해준 후 행들을 담고 있는 node 배열을 돌면서 removed가 true면 X, false면 O를 담아 반환해준다.

3. 코드 보기

import java.util.Stack;

public class Solution {
    class Node {
        Node prev;
        Node next;
        boolean removed;
    }

    public String solution(int n, int k, String[] cmd) {
        StringBuilder sb = new StringBuilder();
        Stack<Node> sta = new Stack<>();
        Node[] node = new Node[n];

        for (int i = 0; i < n; i++) {
            node[i] = new Node();
        }

        for (int i = 0; i < n - 1; i++) {
            node[i + 1].prev = node[i];
            node[i].next = node[i + 1];
        }

        Node cur = node[k];

        for (String str : cmd) {
            char command = str.charAt(0);

            if (command == 'U') {
                int dis = Integer.parseInt(str.substring(2));

                for (int i = 0; i < dis; i++) {
                    cur = cur.prev;
                }
            } else if (command == 'D') {
                int dis = Integer.parseInt(str.substring(2));

                for (int i = 0; i < dis; i++) {
                    cur = cur.next;
                }
            } else if (command == 'C') {
                sta.push(cur);
                cur.removed = true;
                Node up = cur.prev;
                Node down = cur.next;

                if (up != null) {
                    up.next = down;
                }

                if (down != null) {
                    down.prev = up;
                    cur = down;
                } else {
                    cur = up;
                }
            } else { // command == 'Z'
                Node reNode = sta.pop();
                reNode.removed = false;
                Node up = reNode.prev;
                Node down = reNode.next;

                if (up != null) {
                    up.next = reNode;
                }

                if (down != null) {
                    down.prev = reNode;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (node[i].removed) {
                sb.append("X");
            } else {
                sb.append("O");
            }
        }

        return sb.toString();
    }
}