[프로그래머스] 표 편집 (Java)

• 링크: https://school.programmers.co.kr/learn/courses/30/lessons/81303
• 설명: 주어진 표에서 행을 위아래로 선택 이동하고, 현재 선택된 행을 삭제하거나 가장 최근에 삭제된 행을 복구하는 명령어들을 수행한 후의 최종 표 상태를 반환하는 문제다.

◾ 알고리즘 [접근 방식]

단순 접근의 한계

가장 먼저 떠올릴 수 있는 방법은 자바의 ArrayList를 사용하여 표의 행을 관리하는 것이다. 하지만 항상 문제의 제한 사항을 통해 시간 복잡도를 먼저 계산해 보아야 한다.

이 문제에서 처음 표의 행 개수 n은 최대 $1,000,000$이고, 주어지는 명령어 배열 cmd의 크기는 최대 $200,000$이다. 만약 ArrayList를 사용한다면 행을 삭제(C)하거나 복구(Z)할 때마다 뒤에 있는 모든 요소들의 인덱스를 한 칸씩 당기거나 밀어야 한다. 이 경우 삽입/삭제의 시간 복잡도는 $O(N)$이 된다.

최악의 경우, $200,000$번의 명령어 동안 계속해서 리스트의 맨 앞부분을 삭제하고 복구한다면 $1,000,000 \times 200,000 = 200,000,000,000$ (2,000억) 번의 연산이 발생하게 되며, 이는 무조건 시간 초과(Time Limit Exceeded)를 유발한다.

해결책 제시 (이중 연결 리스트 + 스택)

배열이나 리스트의 한계인 삽입/삭제 시간을 단축하기 위해, 포인터만 변경하여 $O(1)$의 시간 복잡도로 삭제와 복구를 수행할 수 있는 이중 연결 리스트(Doubly Linked List)를 사용해야 한다.

1. 왜 이중 연결 리스트인가?: 각 행을 노드(Node)로 만들고 prev와 next 포인터로 연결하면, 특정 노드를 삭제할 때 앞뒤 노드의 포인터만 서로 연결해 주면 되므로 $O(1)$만에 처리할 수 있다.
2. 왜 스택(Stack)인가?: 문제 조건에서 “가장 최근에 삭제된 행부터 복구(Ctrl+Z)”한다고 명시되어 있다. 이는 후입선출(LIFO) 구조인 스택과 완벽하게 일치한다.
3. 복구가 $O(1)$에 가능한 이유: 이중 연결 리스트에서 노드를 삭제하더라도, 삭제된 노드 자신은 여전히 원래의 prev와 next를 기억하고 있다. 스택에서 꺼낸 순서(역순)대로 복구하면 주변 노드들의 상태가 보장되므로, 원래 자리에 그대로 포인터만 다시 연결해 주면 된다.

결과적으로 삭제와 복구를 $O(1)$로 처리하게 되어, 총 시간 복잡도를 명령어 배열을 한 번 순회하는 수준인 $O(K)$ (단, 위아래 이동 칸 수의 합은 $1,000,000$ 이하이므로 안전)로 최적화할 수 있다.

핵심 로직

1. n개의 Node 객체를 생성하고 배열에 담아둔다. (나중에 최종 결과 문자열을 만들 때 순서대로 접근하기 위함)
2. 각 노드의 prev와 next를 초기화하여 이중 연결 리스트를 구성한다. 이때, 맨 앞과 맨 뒤에 각각 더미(Dummy) 노드인 head와 tail을 달아주면 엣지 케이스(맨 처음/끝 요소 삭제) 처리 시 NullPointerException을 방지할 수 있어 코드가 매우 깔끔해진다.
3. 명령어 배열을 순회하며 다음을 수행한다.
   • U / D: prev / next 포인터를 타고 주어진 숫자만큼 이동한다.
   • C (삭제): 현재 노드의 상태를 삭제됨으로 표시하고 스택에 넣는다. 이후 prev와 next 노드를 서로 직접 연결하여 현재 노드를 리스트에서 고립시킨다. 현재 노드가 tail 바로 앞이었다면 위로(prev), 아니면 아래로(next) 이동한다.
   • Z (복구): 스택에서 가장 최근 노드를 꺼내 삭제 상태를 해제한다. 꺼낸 노드가 기억하고 있는 prev와 next를 이용해, 주변 노드들이 다시 자신을 가리키도록 포인터를 복구한다.

◾ 코드

핵심 구현 로직

static void remove() {
    // 1. 상태 변경 및 스택에 저장
    curr.isRemoved = true;
    removed.push(curr);

    // 2. 현재 노드를 리스트에서 분리 (앞뒤 노드를 서로 연결)
    curr.prev.next = curr.next;
    curr.next.prev = curr.prev;

    // 3. 커서 이동 (마지막 행이었다면 윗 행, 아니면 아랫 행)
    if (curr.next == tail) curr = curr.prev;
    else curr = curr.next;
}

static void restore() {
    // 1. 스택에서 가장 최근 삭제된 노드 꺼내기
    Node node = removed.pop();
    node.isRemoved = false;

    // 2. 꺼낸 노드가 기억하는 앞뒤 노드의 포인터를 다시 자신에게 연결
    node.prev.next = node;
    node.next.prev = node;
}

삭제할 때는 앞뒤 노드가 서로 손을 잡게 만들고, 복구할 때는 삭제된 노드가 다시 양옆 노드의 손을 강제로 잡게 만드는 방식이다. 스택의 후입선출 특성 덕분에, node.prev와 node.next가 가리키는 노드들은 복구 시점에 반드시 리스트에 온전히 존재함이 보장된다.

전체 자바 코드

import java.util.*;

class Solution {
    
    // 이중 연결 리스트를 구성할 노드 클래스
    static class Node {
        Node prev;
        Node next;
        boolean isRemoved; // 최종 결과 판별을 위한 삭제 여부 플래그
    }
    
    static Node curr;   // 현재 선택된 노드
    static Node head;   // 더미 헤드 노드
    static Node tail;   // 더미 테일 노드

    static Node[] nodes;            // 인덱스 기반 빠른 접근 및 최종 결과 확인용 배열
    static Stack<Node> removed;     // 삭제된 행을 담아둘 스택 (복구용)

    public String solution(int n, int k, String[] cmds) {
        
        removed = new Stack<>();
        nodes = new Node[n];
        
        // 1. n개의 노드 생성
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node();
        }

        // 2. 더미 head 연결 (Null 처리 로직 생략을 위함)
        head = new Node();
        head.next = nodes[0];
        nodes[0].prev = head;

        // 3. 노드 간의 이중 연결 리스트 구성
        for (int i = 0; i < n - 1; i++) {
            nodes[i].next = nodes[i + 1];
            nodes[i + 1].prev = nodes[i];
        }

        // 4. 더미 tail 연결
        tail = new Node();
        tail.prev = nodes[n - 1];
        nodes[n - 1].next = tail;

        // 초기 커서 위치 설정
        curr = nodes[k];

        // 5. 명령어 처리
        for (String cmd : cmds) {
            char command = cmd.charAt(0);
            
            switch (command) {
                case 'U':
                    up(Integer.parseInt(cmd.substring(2)));
                    break;
                case 'D':
                    down(Integer.parseInt(cmd.substring(2)));
                    break;
                case 'C':
                    remove();
                    break;
                case 'Z':
                    restore();
                    break;
            }
        }

        // 6. 최종 결과 문자열 생성
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (!nodes[i].isRemoved) sb.append("O");
            else sb.append("X");
        }

        return sb.toString();
    }

    // 지정된 칸 수만큼 위로(prev) 이동
    static void up(int offset) {
        for (int i = 0; i < offset; i++) {
            curr = curr.prev;
        }
    }

    // 지정된 칸 수만큼 아래로(next) 이동
    static void down(int offset) {
        for (int i = 0; i < offset; i++) {
            curr = curr.next;
        }
    }

    // 현재 행 삭제
    static void remove() {
        curr.isRemoved = true;
        removed.push(curr);

        // 앞뒤 노드 연결로 현재 노드 끊어내기
        curr.prev.next = curr.next;
        curr.next.prev = curr.prev;

        // 커서 이동: 삭제된 행이 마지막 행인 경우 윗 행을, 아니면 아랫 행을 선택
        if (curr.next == tail) curr = curr.prev;
        else curr = curr.next;
    }

    // 가장 최근 삭제된 행 복구
    static void restore() {
        Node node = removed.pop();
        node.isRemoved = false;

        // 끊어졌던 앞뒤 노드의 포인터를 다시 복구된 노드로 연결
        node.prev.next = node;
        node.next.prev = node;
    }
}

◾ 마무리

이중 연결 리스트는 추가적인 포인터(prev, next)를 유지해야 하므로 단순 배열보다 메모리(공간 복잡도)를 더 많이 사용한다. 하지만 그 공간을 투자한 덕분에 특정 위치에서의 노드 삭제와 복구를 완벽하게 $O(1)$의 속도로 처리할 수 있었다. 공간 복잡도와 시간 복잡도의 완벽한 Trade-off를 보여주는 전형적인 사례다.

특히 이 문제에서 가장 배울 점은 두 가지다. 첫째, 복구(Ctrl+Z) 로직에 스택(Stack)을 활용하여 포인터 꼬임 없이 완벽한 역순 복구를 구현한 점. 둘째, 리스트의 맨 앞이나 맨 뒤를 조작할 때 발생할 수 있는 NullPointerException을 예방하기 위해 더미 노드(Dummy Head & Tail)를 양 끝에 배치하여 조건 분기(if문)를 없애고 코드를 우아하게 만든 점이다. 실전 코딩 테스트에서 이중 연결 리스트를 구현할 때 반드시 기억해야 할 훌륭한 테크닉이다.