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

코딩테스트 연습 - 표 편집

 

 

주요 연산

---

주요 연산은 총 4가지로 다음과 같다

 

1. 커서 위로 이동
2. 커서 아래로 이동
3. 현재 커서 삭제
4. 삭제된 커서 복구

 

처음 테이블이 다음과 같을 때, 모든 연산을 수행한 뒤 마지막에 존재하는 컬럼은 O, 존재하지 않는 컬럼은 X 로 표시해야 한다.

 

연결 리스트로 구현하기

---

행이 삭제되면, 이전 행과 다음 행이 연결되어야 한다. 이것을 만약  ArrayList 나 배열로 구현한다면, 삭제 후 데이터를 한 칸씩 앞으로 이동해야 하기 때문에, 삭제 할 때마다 O(n) 의 시간이 소요될 것이다. cmd 명령어의 개수는 최대 200000개이고, 데이터의 개수는 최대 100만 개 이므로 만약 배열로 구현한다면 시간제한을 통과할 수 없게 된다. 따라서 삭제해도 순서가 유지되도록 연결 리스트로 구현해야 한다.

 

물론 연결 리스트로 구현할 경우 커서 이동에도 O(x) 의 시간이 소요된다. 하지만 문제의 조건에서 cmd 명령어의 커서 이동의 합은 최대 1,000,000 이므로 전혀 문제가 되지 않는다.

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

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

 

index 는 현재 노드의 원래 인덱스 번호이고, prev 와 next 는 연결 리스트 상에서 이전과 다음 노드다.

 

 

연결 리스트 생성

---

public void initLinkedList(int n) {
    root = new Node1(0);
    Node1 prev = root;

    for (int i = 1; i < n; i++) {
        Node1 node = new Node1(i);
        prev.next = node;
        node.prev = prev;
        prev = node;
    }
}

데이터의 개수 n 만큼 노드를 가지는 연결 리스트를 생성한다.

 

커서 이동

---

연결 리스트이기 때문에, 위로 10만번 이동하라는 명령어의 경우 단순히 현재 노드에서 10만번만큼 이전 노드로 가면 된다.

 

public Node1 moveCursor(int degree, boolean up, Node1 cur) {
    while (degree-- > 0) {
        if (up) {
            cur = cur.prev;
        } else {
            cur = cur.next;
        }
    }
    return cur;
}

 

데이터 삭제

---

연결 리스트이기 때문에, 만약 하나의 노드가 삭제될 경우 해당 노드의 이전 노드와, 다음 노드를 서로 연결시켜주면 된다. 이 때 커서의 위치는 다음 데이터로, 만약 다음 데이터가 없을 경우 이전 노드를 가리켜야 하므로 현재 커서가 가르키는 노드를 반환해준다.

 

public Node1 cut(Node1 cur) {
    deletedNodes.add(cur);
    if (null != cur.prev) {
        cur.prev.next = cur.next;
    } else {
        root = cur.next; //삭제된 노드가 루트 노드일 경우, 루트를 변경
    }

    if (null != cur.next) {
        cur.next.prev = cur.prev;
        cur = cur.next; //다음 노드가 있으면 커서를 다음 노드로
    } else {
        cur = cur.prev; //다음 노드가 없으면 커서를 이전 노드로
    }
    //현재 커서를 반환
    return cur;
}

 

데이터 복구

---

만약 복구 명령이 들어올 경우, 가장 최근에 삭제된 노드부터 복구해야 한다. 따라서 Stack으로 삭제된 노드를 관리해야 한다는 것을 알 수 있다. 

삭제된 노드의 경우 복구하면서 이전 노드와 다음 노드를 연결해주고, 이전 노드의 다음 노드와 다음 노드의 이전 노드도 자기한테 연결해주면 된다. 이 때 삭제된 노드가 위의 정보를 모두 가지고 있으므로 복구 작업은 매우 단순하다.

 

public void restore() {
    Node1 node = deletedNodes.pop(); //최근에 삭제된 노드를 꺼낸다
    if (null != node.prev) {
        node.prev.next = node; //삭제된 노드의 이전 노드의 다음 노드를 삭제된 노드로 재연결
    } else {
        root = node; //만약 삭제된 노드가 루트였다면, 루트 변경
    }
    if (null != node.next) {
        node.next.prev = node; //삭제된 노드의 다음 노드와 재연결
    }
}

 

 

 

전체 코드

package per.jongho;

import java.io.IOException;
import java.util.Stack;
import java.util.StringTokenizer;

public class EditTable {

    Node1 root = null;

    Stack<Node1> deletedNodes = new Stack<>();
    final char UP = 'U';
    final char DOWN = 'D';
    final char CUT = 'C';

    public static void main(String[] args) throws IOException {
        EditTable editPyo = new EditTable();
        System.out.println(editPyo.solution(8, 2, new String[]{"D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z", "U 1", "C"}));

    }

    public void initLinkedList(int n) {
        root = new Node1(0);
        Node1 prev = root;

        for (int i = 1; i < n; i++) {
            Node1 node = new Node1(i);
            prev.next = node;
            node.prev = prev;
            prev = node;
        }
    }

    public Node1 getCurrentCursor(int k) {
        Node1 ret = root;
        while (k-- > 0) {
            ret = ret.next;
        }
        return ret;
    }

    /**
     * @param n   처음 표의 행
     * @param k   처음 선택된 행의 위치
     * @param cmd 명령어 문자열 배열
     * @return
     */
    public String solution(int n, int k, String[] cmd) {
        initLinkedList(n);
        Node1 cur = getCurrentCursor(k);

        for (String oper : cmd) {
            cur = operCmd(oper, cur);
        }

        return getAnswer(n);
    }

    public Node1 operCmd(String oper, Node1 cur) {
        StringTokenizer st = new StringTokenizer(oper);
        st.nextToken();
        switch (oper.charAt(0)) {
            case UP:
                cur = moveCursor(Integer.parseInt(st.nextToken()), true, cur);
                break;
            case DOWN:
                cur = moveCursor(Integer.parseInt(st.nextToken()), false, cur);
                break;
            case CUT:
                cur = cut(cur);
                break;
            default:
                restore();
                break;
        }

        return cur;
    }

    public Node1 cut(Node1 cur) {
        deletedNodes.add(cur);
        if (null != cur.prev) {
            cur.prev.next = cur.next;
        } else {
            root = cur.next;
        }

        if (null != cur.next) {
            cur.next.prev = cur.prev;
            cur = cur.next;
        } else {
            cur = cur.prev;
        }
        return cur;
    }

    public void restore() {
        Node1 node = deletedNodes.pop();
        if (null != node.prev) {
            node.prev.next = node;
        } else {
            root = node;
        }
        if (null != node.next) {
            node.next.prev = node;
        }
    }

    public Node1 moveCursor(int degree, boolean up, Node1 cur) {
        while (degree-- > 0) {
            if (up) {
                cur = cur.prev;
            } else {
                cur = cur.next;
            }
        }
        return cur;
    }

    public String getAnswer(int n) {
        boolean[] exist = new boolean[n];
        Node1 cur = root;
        while (cur != null) {
            exist[cur.index] = true;
            cur = cur.next;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(exist[i] ? 'O' : 'X');
        }
        return sb.toString();
    }
}

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

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