문제 링크

첫번째 시도

• 효율성 테스트 마지막 네개를 통과하지 못했다.

코드

import java.util.Stack;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        char[] table = new char[n];
        Stack<Integer> deletedIndexStack = new Stack<>();
        for (int i = 0; i < n; i++) {
            table[i] = 'O';
        }

        int nowIndex = k;
        for (String command : cmd) {
            if (command.equals("C")) {
                table[nowIndex] = 'X';
                deletedIndexStack.push(nowIndex);

                while (++nowIndex < n && table[nowIndex] == 'X') {}

                if (nowIndex >= n) {
                    while (table[--nowIndex] == 'X') {}
                }

            } else if (command.equals("Z")) {
                int deletedIndex = deletedIndexStack.pop();
                table[deletedIndex] = 'O';
            } else { // D X, U X
                String[] moveCmd = command.split(" ");

                nowIndex = moveAndReturnIndex(moveCmd[0], Integer.parseInt(moveCmd[1]), nowIndex, n, table);
//                System.out.println(nowIndex);
            }
        }
        return String.valueOf(table);
    }

    private int moveAndReturnIndex(String direction, int count, int nowIndex, int len, char[] table) {
        int moveCnt = 0;
        if (direction.equals("D")) { // 인덱스 증가
            while (moveCnt != count) {
                while (table[++nowIndex] == 'X') {
                }
                moveCnt++;
            }
        } else { // 인덱스 감소
            while (moveCnt != count) {
                while (table[--nowIndex] == 'X') {
                }
                moveCnt++;
            }
        }

        return nowIndex;
    }
} 

두번째 시도

• 효율성 테스트 한개를 통과하지 못했다.
• 이전에는 char[]에 O, X를 담아서 사용했다면, 이번에는 이전 노드, 다음 노드, 인덱스, O/X 정보가 담긴 Node 배열을 활용하여 코드를 전개했다.
• 즉, 노드와 노드를 연결하고, 삭제할 노드는 연결을 끊어주는 방식으로 풀이했다.

코드

import java.util.Stack;

class Node {
    Node prevNode;
    Node nextNode;
    int index;
    char status;

    public Node(Node prevNode, int index) {
        this.prevNode = prevNode;
        this.nextNode = null;
        this.index = index;
        this.status = 'O';
    }
}

class Solution {
    public String solution(int n, int k, String[] cmd) {
        Node[] table = new Node[n];
        Stack<Integer> deletedIndexStack = new Stack<>();
        // 0번째 노드 : prevNode = null, n - 1번째 노드 : nextNode = null
        table[0] = new Node(null, 0);
        for (int i = 1; i < n; i++) {
            table[i] = new Node(table[i - 1], i);
            table[i - 1].nextNode = table[i];
        }

        Node nowNode = table[k];
        Node prevNode, nextNode;
        for (String command : cmd) {
            if (command.equals("C")) {
                nowNode.status = 'X';
                deletedIndexStack.push(nowNode.index);

                if (nowNode.nextNode == null) {
                    prevNode = nowNode.prevNode;
                    prevNode.nextNode = null;
                    nowNode.prevNode = null;

                    nowNode = prevNode;
                } else if (nowNode.prevNode == null) {
                    nextNode = nowNode.nextNode;
                    nextNode.prevNode = null;
                    nowNode.nextNode = null;

                    nowNode = nextNode;
                } else {
                    prevNode = nowNode.prevNode;
                    nextNode = nowNode.nextNode;
                    prevNode.nextNode = nextNode;
                    nextNode.prevNode = prevNode;
                    nowNode.prevNode = nowNode.nextNode = null;

                    nowNode = nextNode;
                }
            } else if (command.equals("Z")) {
                int deletedIndex = deletedIndexStack.pop();
                table[deletedIndex].status = 'O';
                nextNode = null;
                prevNode = null;

                // nextNode 찾기
                for (int rt = deletedIndex + 1; rt < n; rt++) {
                    if (table[rt].status == 'O') {
                        nextNode = table[rt];
                        break;
                    }
                }

                // prevNode 찾기
                for (int lt = deletedIndex - 1; lt >= 0; lt--) {
                    if (table[lt].status == 'O') {
                        prevNode = table[lt];
                        break;
                    }
                }

                table[deletedIndex].prevNode = prevNode;
                table[deletedIndex].nextNode = nextNode;
                if (prevNode != null) {
                    prevNode.nextNode = table[deletedIndex];
                }
                if (nextNode != null) {
                    nextNode.prevNode = table[deletedIndex];
                }
            } else { // D X, U X
                String[] moveCmd = command.split(" ");

                nowNode = moveAndReturnNowNode(moveCmd[0], Integer.parseInt(moveCmd[1]), nowNode, n, table);
//                System.out.println(nowNode.index);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Node node : table) {
            sb.append(node.status);
        }
        return sb.toString();
    }

    private Node moveAndReturnNowNode(String direction, int count, Node nowNode, int len, Node[] table) {
        int moveCnt = 0;

        if (direction.equals("D")) { // 인덱스 증가
            while (moveCnt != count) {
                nowNode = nowNode.nextNode;
                moveCnt++;
            }
        } else { // 인덱스 감소
            while (moveCnt != count) {
                nowNode = nowNode.prevNode;
                moveCnt++;
            }
        }

        return nowNode;
    }
}

세번째 시도

• 통과
• 제거할 때 prev, next 노드는 연결을 재설정 해야하지만, 제거되는 노드의 연결을 재설정 할 필요가 없다는 사실을 깨달았다. 또한, 이렇게 하면 되돌리기를 할 때 가장 최근에 제거된 노드의 prev, next 노드가 이미 존재하기 때문에 찾는 데에 비용을 소모할 필요가 사라진다.
• 노드와 관련된 로직을 노드 클래스 메소드로 리팩터링하고, 노드리스트 앞뒤에 null 대신 노드를 추가해주면 더 깔끔해 질 것 같다.

import java.util.Stack;

class Node {
    Node prevNode;
    Node nextNode;
    int index;
    char status;

    public Node(Node prevNode, int index) {
        this.prevNode = prevNode;
        this.nextNode = null;
        this.index = index;
        this.status = 'O';
    }
}

class Solution {
    public String solution(int n, int k, String[] cmd) {
        Node[] table = new Node[n];
        Stack<Integer> deletedIndexStack = new Stack<>();
        // 0번째 노드 : prevNode = null, n - 1번째 노드 : nextNode = null
        table[0] = new Node(null, 0);
        for (int i = 1; i < n; i++) {
            table[i] = new Node(table[i - 1], i);
            table[i - 1].nextNode = table[i];
        }

        Node nowNode = table[k];
        Node prevNode, nextNode;
        int deletedIndex;
        for (String command : cmd) {
            if (command.equals("C")) {
                nowNode.status = 'X';
                deletedIndexStack.push(nowNode.index);

                nowNode = delete(nowNode);
            } else if (command.equals("Z")) {
                deletedIndex = deletedIndexStack.pop();
                table[deletedIndex].status = 'O';

                nextNode = table[deletedIndex].nextNode;
                prevNode = table[deletedIndex].prevNode;
//                nextNode = findNextNode(n, table,  deletedIndex);
//                prevNode = findPrevNode(table,  deletedIndex);
//
//                table[deletedIndex].prevNode = prevNode;
//                table[deletedIndex].nextNode = nextNode;
                if (prevNode != null) {
                    prevNode.nextNode = table[deletedIndex];
                }
                if (nextNode != null) {
                    nextNode.prevNode = table[deletedIndex];
                }
            } else { // D X, U X
                String[] moveCmd = command.split(" ");

                nowNode = move(moveCmd[0], Integer.parseInt(moveCmd[1]), nowNode, n, table);
//                System.out.println(nowNode.index);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Node node : table) {
            sb.append(node.status);
        }
        return sb.toString();
    }

    private Node findPrevNode(Node[] table, int index) {
        Node prevNode = null;
        for (int lt = index - 1; lt >= 0; lt--) {
            if (table[lt].status == 'O') {
                prevNode = table[lt];
                break;
            }
        }
        return prevNode;
    }

    private Node findNextNode(int n, Node[] table, int index) {
        Node nextNode = null;
        for (int rt = index + 1; rt < n; rt++) {
            if (table[rt].status == 'O') {
                nextNode = table[rt];
                break;
            }
        }
        return nextNode;
    }

    private Node delete(Node nowNode) {
        if (nowNode.nextNode == null) {
            nowNode.prevNode.nextNode = null;

            nowNode = nowNode.prevNode;
        } else if (nowNode.prevNode == null) {
            nowNode.nextNode.prevNode = null;

            nowNode = nowNode.nextNode;
        } else {
            nowNode.prevNode.nextNode = nowNode.nextNode;
            nowNode.nextNode.prevNode = nowNode.prevNode;

            nowNode = nowNode.nextNode;
        }
        return nowNode;
    }

    private Node move(String direction, int count, Node nowNode, int len, Node[] table) {
        int moveCnt = 0;

        if (direction.equals("D")) { // 인덱스 증가
            while (moveCnt != count) {
                nowNode = nowNode.nextNode;
                moveCnt++;
            }
        } else { // 인덱스 감소
            while (moveCnt != count) {
                nowNode = nowNode.prevNode;
                moveCnt++;
            }
        }

        return nowNode;
    }
}