Linked List 개념을 활용한 문제 풀이 (프로그래머스, 2021 카카오 인턴십 표 편집)

아래의 문제를 LinkedList를 활용해서 풀다가 시간 초과가 발생하며 배운 점을 간단하게 기록하고자합니다.

프로그래머스

 

문제 상황에는 List 내의 삽입과 제거가 빈번하게 발생하기 때문에, 당연히 LinkedList 를 활용해야겠다고 생각했지만 시간초과가 발생했습니다.

 

그 이유는 Java의 LinkedList 자료구조에서 삽입과 제거가 O(1)의 시간복잡도로 수행할 수 있는 것은 맞지만, 해당 위치로 이동하는데에 O(n)의 시간이 소요되기 때문입니다. 

예를 들면 add(index, 추가할 자료),  remove(index), set(index, 추가할 자료)와 같은 함수들은, 우선 해당 노드로 이동(O(n))한 뒤 작업을 진행합니다.

 

이 작업을 빠르게 해결하려면 해당 노드로 빠르게 접근하는 방법이 필요하고, 위의 문제에서는 현재 행 위치(즉 해당 노드의 주소)를 계속해서 트래킹하여 O(1)로 삽입/제거 작업을 수행할 수 있습니다.

 

이는 노드에 앞 노드와 뒷 노드의 주소를 가지고 있도록 직접 클래스를 구현해서 해결할 수 있습니다.

 

저는 아래처럼 구현했습니다.

class Record {
    int id;
    Record before;
    Record after;

    Record(int id) {
        this.id = id;
    }
}

 

전체 풀이 코드는 다음고 같습니다.

import java.util.*;

class Solution {
    class Record {
        int id;
        Record before;
        Record after;
        
        Record(int id) {
            this.id = id;
        }
    }
    
    Stack<Record> records = new Stack<>(); // 삭제한 기록을 저장
    Record current = new Record(0);
    boolean[] isDeleted;
    
    public String solution(int n, int k, String[] cmd) {
        initTable(n);
        moveAfter(k);
        isDeleted = new boolean[n];
        
        for (int i = 0; i < cmd.length; i++) {
            execute(cmd[i]);
        }

        String answer = makeAnswer();
        return answer;
    }
    
    private String makeAnswer() {
        StringBuilder sb = new StringBuilder();
        for (boolean d : isDeleted) {
            sb.append(d ? "X" : "O");
        }
        return sb.toString();
    }
    
    private void initTable(int n) {
        Record before = this.current;
        
        for (int i = 1; i < n; i++) {
            Record current = new Record(i);
            before.after = current;
            current.before = before;
            before = current;
        }
    }
    
    private void execute(String command) {
        char type = command.charAt(0);
        
        switch(type) {
            case 'U':
                moveBefore(extractOffset(command));
                break;
            case 'D':
                moveAfter(extractOffset(command));
                break;
            case 'C':
                delete();
                break;
            case 'Z':
                undo();
                break;
        }
    }
    
    private void undo() {
        Record target = records.pop();
        if (target.before != null) target.before.after = target;
        if (target.after != null) target.after.before = target;
        isDeleted[target.id] = false;
    }
    
    private void delete() {
        isDeleted[current.id] = true;
        records.push(current);
        if (current.before != null) {
            current.before.after = current.after;    
        }
        if (current.after != null) {
            current.after.before = current.before;
            current = current.after;
        } else {
            current = current.before;
        }
    }
    
    
    private void moveAfter(int offset) {
        for (int i = offset; i > 0; i--) {
            current = current.after;
        }
    }
    
    private void moveBefore(int offset) {
        for (int i = offset; i > 0; i--) {
            current = current.before;
        }
    }
    
    private int extractOffset(String command) {
        return Integer.parseInt(command.split(" ")[1]);
    }
}