[Algorithm] 프로그래머스 - 표 편집 자바

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래머스 표 편집을 자바로 풀이한 과정을 정리하고자 합니다.

 

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/81303#

프로그래머스

 

 

1. 풀이 소스

 

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        Graph graph = new Graph(n, k);
        graph.run(cmd);
        return graph.getStatus();
    }
}

class Graph {

    Point point; // 현재 위치한 포인트를 기록
    Node start; // 시작 노드 (삭제하거나 다시 복구하는 과정에서 살아있는 맨 앞의 노드)
    Node last; // 마지막 노드 (삭제하거나 다시 복구하는 과정에서 살아있는 맨 뒤의 노드)
    Node[] nodes; // 노드를 설정할 입력 배열
    Stack<Node> dels = new Stack<>(); // 후입선출 복구를 위한 스택

    class Node {
        boolean isDel; // 출력을 위해 삭제 여부 기록
        Node pre; // 이전 노드
        Node next; // 마지막 노드
        Node () {}
    }

    class Point {
        Node p; // 현재 포인트의 노드
        Point(Node p) {
            this.p = p;
        }
    }

    Graph(int n, int k) {
        nodes = new Node[n];

        for (int i = 0; i < n; i++) nodes[i] = new Node();
        nodes[0].next = nodes[1];
        for (int i = 1; i < n - 1; i++) {
            nodes[i].pre = nodes[i - 1]; // nodes 배열에 i 인덱스에 있는 노드에 노드 연결
            nodes[i].next = nodes[i + 1];
        }
        
        nodes[n - 1].pre = nodes[n - 2];
        point = new Point(nodes[k]);
        start = nodes[0]; // start 초기화
        last = nodes[n - 1]; // last 초기화
    }

    void up(int dx) {
        Node node = point.p; // 현재 위치한 노드
        Node pre = node;
        int p = 0;
        while(p < dx) {
            pre = pre.pre; // up 은 행을 올려야 하므로 이전 노드로 탐색
            p++; 
        }

        point.p = pre;
    }

    void down(int dx) {
        Node node = point.p;
        Node next = node;
        int p = 0;
        while(p < dx) {
            next = next.next; // down은 행을 내려야 하므로 다음 노드로 탐색
            p++;
        }

        point.p = next;
    }

    // 위치한 노드에서 제거
    void del() {
        Node node = point.p;

        if (node == start) { // 만약 맨 앞의 노드가 삭제될 경우 해당 노드의 다음를 start로 설정
            start = node.next; 
            start.pre = null;
            point.p = start;
        } else if (node == last) {
            last = node.pre;
            last.next = null;
            point.p = last; // 마지막 인덱스의 경우 앞으로 이동
        } else {
            node.next.pre = node.pre; // 삭제되는 노드의 이전 노드와 다음 노드 연결
            node.pre.next = node.next;
            point.p = node.next; // 삭제되는 노드의 다음 노드로 포인트 변경
        }

        node.isDel = true; // 삭제 여부 표시
        dels.push(node); // 스택에 넣기
    }

    void restore() {
        Node node = dels.pop(); // 삭제된 노드 후입선출
        node.isDel = false; // 복구 설정

        if (node.pre != null && node.next != null) { // 중간에 위치한 노드인경우
            Node pre = node.pre; 
            Node next = node.next;
            pre.next = node; // 이전 노드의 다음 노드를 node로 복구
            next.pre = node; // 다음 노드의 이전 노드를 node로 복구
        } else if (node.pre != null) { // next == null
            Node pre = node.pre; 
            pre.next = node;
            last = node; // 마지막 노드 업데이트
        } else if (node.next != null) {
            Node next = node.next;
            next.pre = node;
            start = node; // 첫번째 노드 업데이트
        }
    }

    void run(String[] cmds) {
        for (String cmd : cmds) {
            char command = cmd.charAt(0);
            if (cmd.length() > 1) {
                int num = Integer.parseInt(cmd.split(" ")[1]);
                if (command == 'D') down(num);
                else up(num);
            }

            else {
                if (command == 'C') del();
                else restore();
            }
        }

    }

    String getStatus() {
        StringBuilder sb = new StringBuilder();
        for (Node node : nodes) {
            if (node.isDel) sb.append("X");
            else sb.append("O");
        }

        return sb.toString();
    }
}

 

 

 

2. 풀이 과정

 

해당 문제를 읽고 LinkedList를 사용하거나 ArrayList를 사용할 경우 삭제한 노드를 복구하는 과정에서 시간초과가 발생할 것 같다는 생각을 하였습니다. 따라서, LinkedList를 직접 구현하여, 만약 삭제 후 복구를 해야 한다면, 스택에서 노드를 가져온 후,
연결관계를 기억한 노드에 다시 연결관계를 설정해주는 것이 좋을 것 같다는 생각을 하였습니다. 따라서, 노드를 저장할 배열을 설정한 후, 연결관계를 설정하고 pre와 next로 인스턴스를 설정하여 문제를 해결하였습니다.

 

삭제 및 복구하는 과정에 대한 자세한 내용을 정리하면 다음과 같습니다.

• 만약 OOOOO 상황에서 포인트가 인덱스 2에 위치한 경우, OOXOO가 설정되게 됩니다.
• 이 과정에서 2번 인덱스의 이전, 다음 노드인 1번 3번 노드는 서로 연결 시켜 주어야 합니다.
• 따라서, 1번 노드.next = 3번 노드, 3번 노드. pre = 1번 노드로 설정할 수 있습니다.
• 복구하는 과정에서는 '후입선출'이므로, 2번 노드가 삭제되는 시점에 이전, 이후 노드는
  반드시 2번 노드가 다시 복구된다면 두 노드도 살아있게 됩니다.
  
  삭제: OOXOO -> OXXOO -> OXXXO 상태
  복구: OXXOO -> OOXOO (후입선출)

 

따라서, 삭제되는 시점에는 삭제되는 노드의 연관관계를 바꾸지 않는다면 다시 복구하는 과정을 설정할 수 있습니다.

기타 다른 부분들은 1번 풀이에 자세한 주석으로 작성하였습니다.

 

 

 

3. 더 좋은 코드 공유

 

 

테스트는 통과하였지만, 최대 약 325ms가 걸렸습니다.

다른 블로그에 더 좋은 풀이로 작성하신 코드가 있어 공유드립니다.

 

https://moonsbeen.tistory.com/294

[프로그래머스]표 편집 - JAVA

 

해당 블로거분의 코드를 실행하면 효율성 테스트 기준 무려 100ms 평균으로 통과할 수 있는 코드입니다.

 

이상으로 해당 문제에 대한 리뷰를 마치도록 하였습니다. 감사합니다.!