Java - [프로그래머스]81303 - Lv3.표 편집

출처

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

프로그래머스

 

 

문제

 

이 문제는 n개의 노드가 연결된 링크드 리스트에서, 주어진 명령어들을 처리하여 선택/삭제/복구의 과정을 거쳐 리스트의 상태를 업데이트하고, 마지막 상태를 출력하는 문제입니다.

 

풀이

커서가 돌아다니면서, 표 중간에 있는 데이터를 삭제하거나 복구 시 다시 끼워넣어야 하는 문제입니다. 가장 먼저 떠올릴 수 있는 자료 구조는 바로 연결리스트(Linked List)였습니다.

 

연결 리스트는 앞 뒤 노드에 대한 정보를 가지고 있기 때문에, 삭제와 삽입이 상대적으로 간편하다는 장점이 있습니다.

 

자바에 있는 연결리스트가 아닌, 직접 구현하여 문제를 해결해보겠습니다. 먼저, 연결리스트를 구현하기 위한 Node 자료형을 선언합니다.

class Node {
    Node prev = null;
    Node next = null;
    boolean isDeleted;
}

 

이 문제에서 삭제된 노드는 복구할 수 있어야 하기 때문에, 앞 뒤 노드에 대한 정보를 지우는 대신 삭제 상태를 확인할 수 있는  isDeleted 행을 추가하였습니다.

 

이제 표에 주어진 정보를 연결 리스트로 표현하고, 버려진 정보를 저장할 Stack을 만들고 현재 커서의 정보를 나타내는 now 변수도 선언합니다.

// 원본 표의 정보를 저장할 배열
nodeArr = new Node[1000001];

nodeArr[0] = new Node();
for (int i = 1; i < n; i++) {
    nodeArr[i] = new Node();
    nodeArr[i].prev = nodeArr[i-1];
    nodeArr[i-1].next = nodeArr[i];
}
// 버려진 노드
Stack<Node> trash= new Stack<>();
// 현재 커서가 위치한 노드
Node now = nodeArr[k];

 

이제, 명령어 별로 작업을 수행하도록 합니다.

 

U 명령어

 if (type == 'U') {
    int cnt = Integer.parseInt(query.substring(2));
    for (int i = 0 ; i < cnt; i++)
        now = now.prev;
}

 

지정된 숫자만큼  prev로 돌아갑니다.

 

D 명령어

else if (type == 'D') {
    int cnt = Integer.parseInt(query.substring(2));
    for (int i = 0 ; i < cnt; i++) {
        now = now.next;
    }
}

 

U와 마찬가지로 지정된 숫자만큼 next로 이동합니다.

 

C 명령어

else if (type == 'C') {
    now.isDeleted = true;
    trash.push(now);

    Node next = now.next;
    Node prev = now.prev;
    if (prev != null) {
        prev.next = next;
    }
    if (next != null) {
        next.prev = prev;
        now = next;
    } else {
        now = prev;
    }
}

 

중간에 있는 노드를 삭제하는 명령어입니다. 지울 노드의 isDeleted 상태를 true로 바꾸어 줍니다. 이후 아래의 단계를 따릅니다.

• prev Node -> 지울 Node -> next Node 처럼 연결되어 있는 형태에서 , Node를 중간에서 빼고 prev -> next의 형태로 연결
• 이때 prev Node.next는 next Node로 연결하고, next Node.prev 는 prev Node로 연결

 

Z 명령어

else if(type == 'Z') {
    Node node = trash.pop();
    Node prev=node.prev;
    Node next=node.next;

    node.isDeleted=false;
    if(prev!=null){
        prev.next=node;
    }
    if(next!=null){
        next.prev=node;
    }
}

 

삭제되었던 노드를 복구하는 명령어 입니다. 버려진 노드를 저장했던 Stack에서 pop 하여, 상태를 변경하고 아래와 같은 단계를 따릅니다.

 

삭제되기 전 prev와 next 노드에 대한 정보를 가지고 있기 때문에, 이를 토대로 다시 prev.next와 next.prev를 자신으로 설정함으로써 중간에 연결을 이어줍니다.

 

마지막은 노드들의 상태를 문자열로 만들어 반환합니다

 StringBuilder sb = new StringBuilder();
for(int i=0;i<n;i++){
    if(nodeArr[i].isDeleted) sb.append('X');
    else sb.append('O');
}

return sb.toString();

 

전체 코드 

import java.util.*;

class Solution {
    
    private Node[] nodeArr;
    
    public String solution(int n, int k, String[] cmd) {
        nodeArr = new Node[1000001];
        nodeArr[0] = new Node();
        for (int i = 1; i < n; i++) {
            nodeArr[i] = new Node();
            nodeArr[i].prev = nodeArr[i-1];
            nodeArr[i-1].next = nodeArr[i];
        }
        
        Stack<Node> trash= new Stack<>();
        Node now = nodeArr[k];
        
        for (String query : cmd) {
            char type = query.charAt(0);
            if (type == 'U') {
                int cnt = Integer.parseInt(query.substring(2));
                for (int i = 0 ; i < cnt; i++)
                    now = now.prev;
            }
            else if (type == 'D') {
                int cnt = Integer.parseInt(query.substring(2));
                for (int i = 0 ; i < cnt; i++) {
                    now = now.next;
                }
            } else if (type == 'C') {
                now.isDeleted = true;
                trash.push(now);

                Node next = now.next;
                Node prev = now.prev;
                if (prev != null) {
                    prev.next = next;
                }
                if (next != null) {
                    next.prev = prev;
                    now = next;
                } else {
                    now = prev;
                }
            } else if(type == 'Z') {
                Node node = trash.pop();
                Node prev=node.prev;
                Node next=node.next;

                node.isDeleted=false;
                if(prev!=null){
                    prev.next=node;
                }
                if(next!=null){
                    next.prev=node;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++){
            if(nodeArr[i].isDeleted) sb.append('X');
            else sb.append('O');
        }
        
        return sb.toString();
    }
    
    class Node {
        Node prev = null;
        Node next = null;
        boolean isDeleted;
    }
}