문제

문제링크

구현은 문제가 없으나, 효율성을 생각하면서 풀어야 하는 문제입니다.
자료구조에 대해 다시한번 생각해 볼 수 있어서 어려웠지만 좋은 문제였다고 생각합니다.

풀이

접근 방법

실패한 기록들

1. 구현 자체는 문제가 없을거라 생각하고 ArrayList로 구현
   -> 효율성에서 실패
2. 삭제, 되돌리기에서 시간이 많이 소요된다 생각하고 단순하게 LinkedList로 변경
   -> 또 효율성에서 실패

둘 모두 인덱스를 가지고 진행해서 삭제를 진행할 때, 되돌리기를 진행할 때 시간을 많이 잡아먹을 수 밖에 없습니다.

핵심은 연결 리스트 구현

따라서 C언어에서 구현했던 연결 리스트처럼, 현재 노드(위치)를 가지고 삭제, 되돌리기를 진행한다면 효율성을 만족할 수 있습니다.

Node 클래스엔 다음과 같은 필드가 있습니다.

class Node {
	Node prev; // 이전 노드
    Node next; // 다음 노드
    boolean isRemoved; // 정답 포맷을 만들기 위한 불리안 필드
}

그리고 이런 노드들을 관리해주는, 즉 연결리스트 클래스도 하나 만들어줬습니다.

class LinkedList {
        List<Node> answerTable = new ArrayList<>(); // 추후설명
        Node temp; // 임시 노드 보관
        Node now; // 현재 위치(커서)

        public LinkedList(int size, int cursor) {
            temp = null;
            for (int i = 0; i < size; i++) {
                addNode();
                if (i == cursor) {
                    now = temp;
                }
            }
        }

        public void addNode() {
            Node newNode = new Node(temp, null);
            answerTable.add(newNode);
            // 처음 노드를 넣을 때는 제외한다.
            if (temp != null) {
                temp.next = newNode; // 이전 노드의 다음을 추가한 노드로
            }
            temp = newNode;
        }

구현

삭제

삭제는 다음과 같이 진행됩니다.

• 현재 노드를 스택에 저장합니다.
  그 이유는 되돌리기가 마지막에 삭제된게 먼저 복구되는, LIFO 방식이기 때문입니다.

• 그 다음, 위 그림과 같이 연결을 변경합니다.
  1. 현재노드의 prev노드의 next를 현재노드의 next로 변경합니다.
  2. 현재노드의 next노드의 prev를 현재노드의 prev로 변경합니다.
  🚨주의점🚨 맨 앞, 맨 뒤 노드를 삭제할 때는 null처리를 해줘야 합니다.
  

• 그 후, now(현재위치)를 변경해줍니다.
  1. 일반적인 경우는 삭제 후 next 노드로 now를 변경하지만, 맨 마지막 노드가 삭제된 경우는 prev 노드로 now를 변경합니다.
  

public void delete(Stack<Node> removed) {
            now.isDelete = true;
            removed.add(now);
            // n o n 사실 필요없다. 조건에서 안준다고 명시했기 떄문.
            if (now.next == null && now.prev == null) {
                return;
            }
            // o o n
            else if (now.next == null) {
                now.prev.next = null;
                now = now.prev; // 맨 마지막은
            }
            // n o o
            else if (now.prev == null) {
                now.next.prev = null;
                now = now.next;
            }
            // o o o
            else {
                now.prev.next = now.next;
                now.next.prev = now.prev;
                now = now.next;
            }
        }

되돌리기

되돌리기는 연결 리스트로 구현했기 때문에 많이 쉬워졌습니다. 현재 위치도 변하지 않으니 스택에 저장해놨던 것들을 하나씩 꺼내서 연결시켜줍니다.

여기서 핵심은 스택에 있는 삭제된 노드는 삭제된 시점의 prev와 next 노드를 기억하고 있다는 점 입니다. 따라서 다음과 같이 접근할 수 있습니다.

이렇게 복구를 진행할 수 있고, 코드는 다음과 같습니다.

public void restore(Node node) {
            node.isDelete = false;
            if (node.prev != null) { // 맨 처음 노드가 아니라면
                node.prev.next = node;
            }
            if (node.next != null) { // 맨 마지막 노드가 아니라면
                node.next.prev = node;
            }
        }

정답 포맷 만들기

여기가 은근 골칫거리인데, 처음엔 노드마다 int 필드를 하나 추가해서 순서를 저장해 연결 리스트와 삭제된 노드 스택을 모두 순회하면서 StringBuilder를 조립하며 진행했습니다.

하지만 StringBuilder의 set,insert 모두 탐색을 진행해야 해서 O(N)의 시간복잡도를 가지므로
(연결 리스트 탐색 + 스택 탐색) * (StringBuilder set 또는 insert)
의 시간 복잡도는 무리가 있다고 판단했습니다.

그래서 검색을 하며 처음부터 연결 리스트의 노드들을 모두 리스트에 저장하고 append를 사용하는 방식을 찾아냈습니다.

class LinkedList {
        List<Node> answerTable = new ArrayList<>();
        ...
}

class Node {
      boolean isDeleted; // 삭제되어 스택으로 들어가면 true로
      ...
}

class Solution {

      for (int i = 0; i < n; i++) {
          if (linkedList.answerTable.get(i).isDelete) {
              answer.append("X");
          } else {
              answer.append("O");
          }
      }
}

이렇게 만들면 (연결리스트의 isDeleted검사) * (StringBuilder append(O(1)) 의 매우 빠른 속도로 정답을 만들 수 있습니다. 따로 순서를 저장하는 필드가 필요없는 것도 장점입니다.

마치며

자료구조를 직접 구현해보는 것도 중요하다는 것을 깨달았습니다. 컬렉션에 의존하지말고 기초적인 부분 역시 다시한번 점검해야겠습니다.
처음 그림을 그려보며 글을 작성했는데, 원래 KeyNote로 작성하는게 맞는지 모르겠습니다. 부족한 글과 그림 잘 봐주셔서 감사합니다. 틀린게 있으면 꼭 알려주세요!!

전체 코드

최적화 코드

import java.io.*;
import java.util.*;

class Solution {
    
public String solution(int n, int k, String[] cmd) {
        StringBuilder answer = new StringBuilder();

        LinkedList linkedList = new LinkedList(n, k);
        Stack<Node> removed = new Stack<>();

        for (int i = 0; i < cmd.length; i++) {
            StringTokenizer st = new StringTokenizer(cmd[i]);
            String command = st.nextToken();

            if (command.equals("U")) {
                linkedList.movePrev(Integer.parseInt(st.nextToken()));
            } else if (command.equals("D")) {
                linkedList.moveNext(Integer.parseInt(st.nextToken()));
            } else if (command.equals("C")) {
                linkedList.delete(removed);
            } else if (command.equals("Z")) {
                linkedList.restore(removed.pop());
            }
        }

        for (int i = 0; i < n; i++) {
            if (linkedList.answerTable.get(i).isDelete) {
                answer.append("X");
            } else {
                answer.append("O");
            }
        }
        
        return answer.toString();
    }
}

    class LinkedList {

        List<Node> answerTable = new ArrayList<>();
        Node temp;
        Node now;
        int size;

        public LinkedList(int size, int cursor) {
            temp = new Node(null, null);
            this.size = size;
            for (int i = 0; i < size; i++) {
                addNode();
                if (i == cursor) {
                    now = temp;
                }
            }
        }

        public void addNode() {
            Node newNode = new Node(temp, null);
            answerTable.add(newNode);
            if (temp != null) {
                temp.next = newNode;
            }
            temp = newNode;
        }

        public void moveNext(int number) {
            for (int i = 0; i < number; i++) {
                now = now.next;
            }
        }

        public void movePrev(int number) {
            for (int i = 0; i < number; i++) {
                now = now.prev;
            }
        }

        public void delete(Stack<Node> removed) {
            now.isDelete = true;
            removed.add(now);
            // n o n 사실 필요없다. 조건에서 안준다고 명시했기 떄문.
            if (now.next == null && now.prev == null) {
                return;
            }
            // o o n
            else if (now.next == null) {
                now.prev.next = null;
                now = now.prev;
            }
            // n o o
            else if (now.prev == null) {
                now.next.prev = null;
                now = now.next;
            }
            // o o o
            else {

                now.prev.next = now.next;
                now.next.prev = now.prev;
                now = now.next;
            }
        }

        public void restore(Node node) {
            node.isDelete = false;
            if (node.prev != null) {
                node.prev.next = node;
            }
            if (node.next != null) {
                node.next.prev = node;
            }
        }
    }

class Node {
    Node prev;
    Node next;
    boolean isDelete;
    
    public Node(Node prev, Node next) {
        this.prev = prev;
        this.next = next;
    }
}

제출 코드

import java.io.*;
import java.util.*;

class Solution {
    
public String solution(int n, int k, String[] cmd) {
        StringBuilder answer = new StringBuilder();

        LinkedList linkedList = new LinkedList(n, k);
        Stack<Node> removed = new Stack<>();

        for (int i = 0; i < cmd.length; i++) {
            StringTokenizer st = new StringTokenizer(cmd[i]);
            String command = st.nextToken();

            if (command.equals("U")) {
                linkedList.movePrev(Integer.parseInt(st.nextToken()));
            } else if (command.equals("D")) {
                linkedList.moveNext(Integer.parseInt(st.nextToken()));
            } else if (command.equals("C")) {
                linkedList.delete(removed);
            } else if (command.equals("Z")) {
                linkedList.restore(removed.pop());
            }
        }
        // linkedList.print();

        for (int i = 0; i < n; i++) {
            if (linkedList.answerTable.get(i).isDelete) {
                answer.append("X");
            } else {
                answer.append("O");
            }
        }
        
        return answer.toString();
    }
}

    class LinkedList {

        List<Node> answerTable = new ArrayList<>();
        Node head;
        Node temp;
        Node now;
        int size;

        public LinkedList(int size, int cursor) {
            head = new Node(0, null, null);
            answerTable.add(head);
            temp = head;
            this.size = size;
            for (int i = 1; i < size; i++) {
                addNode(i);
                if (i == cursor) {
                    now = temp;
                }
            }
        }

        public void addNode(int data) {
            Node newNode = new Node(data, temp, null);
            answerTable.add(newNode);
            temp.next = newNode;
            temp = temp.next;
        }

        public void moveNext(int number) {
            for (int i = 0; i < number; i++) {
                now = now.next;
            }
        }

        public void movePrev(int number) {
            for (int i = 0; i < number; i++) {
                now = now.prev;
            }
        }

        public void delete(Stack<Node> removed) {
            now.isDelete = true;
            removed.add(now);
            // n o n 사실 필요없다. 조건에서 안준다고 명시했기 떄문.
            if (now.next == null && now.prev == null) {
                return;
            }
            // o o n
            else if (now.next == null) {
                now.prev.next = null;
                now = now.prev;
            }
            // n o o
            else if (now.prev == null) {
                now.next.prev = null;
                now = now.next;
            }
            // o o o
            else {
                Node temp = now.next;
                now.prev.next = now.next;
                now.next.prev = now.prev;
                now = temp;
            }
        }

        public void restore(Node node) {
            node.isDelete = false;
            if (node.prev != null) {
                node.prev.next = node;
            }
            if (node.next != null) {
                node.next.prev = node;
            }
        }

        public void print() {
            temp = head;
            int count = 0;
            while (temp != null) {
                System.out.println("print" + count + " , " + temp.data);
                temp = temp.next;
                count++;
            }
            System.out.println("now = " + now.data);
        }
    }

class Node {
    Node prev;
    Node next;
    int data;
    boolean isDelete;
    
    public Node(int data, Node prev, Node next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}

Reference

https://jangcenter.tistory.com/125