[프로그래머스] 2021 카카오 채용연계형 인턴십 - 표 편집 - 자바(JAVA)

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

코딩테스트 연습 - 표 편집

 

문제 해석

표의 행을 선택, 삭제 , 복구하는 프로그램을 작성해야 합니다.

 

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

위의 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다.

한 번의 한 행만 선택할 수 있으며, 표의 범위를 벗어날 수 없습니다.

 

다음과 같은 명령어를 사용하여 표를 편집합니다.

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

 

이후에 최종 표 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O 삭제된 행은 X로 표시합니다.

이를 문자열 형태로 return하세요

 

문제 풀이 전 설계

삽입 삭제가 빈번하게 발생하기 때문에 LinkedList를 사용하려고 합니다.

그리고 복구를 위한 Previous Index와 Value를 저장해두려고 합니다.

아래행을 선택하는 과정에 예외처리만 조심하면 될 것 같습니다.

 

최종 값과 처음 값 비교는 Set을 하나 선언하여 비교하면 될 것 같습니다.

이때 기본 문자열을 제공해주지 않기 때문에 가장 간단한 생각으로는 임의의 0~N-1까지 가지는 문자열을 만들어 버릴까 생각이 듭니다.

하지만 시간 복잡도를 고려했을 때 LinkedList의 삭제 시간 복잡도는 O(N)입니다.

100,000 * 200,000 = 20,000,000,000 (20억)으로 시간 초과가 예상됩니다.

 

문제 풀이하면서 

양방향 연결 리스트를 직접 구현해야 하는 문제였습니다.

Java에서 구현된 LinkedList도 양방향으로 구현되어 있지만 여기서는 curPoint라는 현재 위치를 계속 추적하기 위해서 따로 구현해야 풀 수 있었습니다.

 

코드

import java.util.*;

public class Solution_표편집 {
    public static void main(String[] args) {
        int n = 8;
        int k = 2;
        String[] cmd = {"D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z"};

        Deque<Node> history = new LinkedList<>();
        Node root = new Node(0);
        Node prev = root;
        Node curPoint = root;

        for (int i = 1; i < n; i++) {
            Node cur = new Node(i);
            prev.next = cur;
            cur.prev = prev;
            prev = cur;
            if (i == k) curPoint = cur;
        }
        StringTokenizer st = null;
        for (String query : cmd) {
            st = new StringTokenizer(query," ");
            switch (st.nextToken()) {
                case "U": {
                    int x = Integer.parseInt(st.nextToken());
                    while (x > 0) {
                        curPoint = curPoint.prev;
                        x--;
                    }
                    break;
                }
                case "D": {
                    int x = Integer.parseInt(st.nextToken());
                    while (x > 0) {
                        curPoint = curPoint.next;
                        x--;
                    }
                    break;
                }
                case "C": {
                    history.addLast(curPoint);
                    curPoint = curPoint.delete();
                    break;
                }
                case "Z": {
                    history.pollLast().restore();
                    break;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append('O');
        }
        while (!history.isEmpty()) {
            Node temp = history.pollLast();
            sb.setCharAt(temp.value, 'X');
        }
        System.out.println(sb.toString());
    }
}

class Node {
    Node prev,next;
    int value;

    Node(int index) {
        this.prev = null;
        this.next = null;
        this.value = index;
    }

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

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