프로그래머스 LV3 표병합

https://school.programmers.co.kr/learn/courses/30/lessons/81303?language=java

링크드리스트를 활용해서 나타냈어야 하는 문제였습니다.

for (int i = 0; i < n; i++) {
            arr[i] = new Node(i,i);
    }

public static class Node {
        int e;
        int next;
        int prev;
        Node (int e, int c) {
            this.e  = e;
            this.prev = c - 1;
            this.next = c + 1;
        }
   }

노드들의 이전값과 다음 값을 저장하는 링크드리스트를 구현하여 삭제시에 해당 노드의 이전 노드와 다음 노드의 next,prev를 수정하는 방식으로 활용하려고 했습니다.

 if (arr[idx].prev < 0) {
                   arr[arr[idx].next].prev = arr[idx].prev;  
                   idx = arr[idx].next;
 }
 else if (arr[idx].next >= n) {
                   arr[arr[idx].prev].next = arr[idx].next; 
                   idx = arr[idx].prev;
 }
 else {
                    arr[arr[idx].prev].next = arr[idx].next;
                    arr[arr[idx].next].prev = arr[idx].prev;      
                    idx = arr[idx].next;
}

삭제 연산 시에 맨 앞의 노드와 맨 뒤의 노드에서는 각각 이전 노드와 다음 노드가 존재하지 않기에 분기처리를 해주는 것이 까다로웠던 것 같습니다.

캐싱한 걸 읽어오는 것은 스택을 활용해서 제일 최근의 노드를 복원하는 방식으로 구현했습니다.

                 q.add(arr[idx]);
                 isDelete[arr[idx].e] = true;

boolean형의 배열에 삭제되었다는 표시와 스택에 삭제 노드를 넣어주고

            else {
                Node r = q.pop();
                isDelete[r.e] = false;
                if(r.prev > -1) {
                    arr[r.prev].next = r.e;
                }
                if(r.next < n){
                   arr[r.next].prev = r.e; 
                }  
            }

복원을 할 시엔 위와 같이 이전 노드의 다음 값과 다음 노드의 이전 값을 삭제노드로 연결해준다.

위아래로 움직이는 로직은

    if (s[0].equals("U")) {
                int t = Integer.parseInt(s[1]);
                for(int c = 0; c < t; c++) {
                    idx = arr[idx].prev;
                }
    }
    else if (s[0].equals("D")) {
                int t = Integer.parseInt(s[1]);
                for(int c = 0; c < t; c++) {
                    idx = arr[idx].next;
                }           
    }

처럼 계속해서 다음 또는 이전 노드를 수만큼 움직이면 된다.

시간이 많이 걸린 부분은 맨 마지막 노드에서 삭제연산시 이전 노드로 움직여야 했는데 이거에 대한 기준점을 못잡아 2개의 테케에서 런타임에러가 났었다.

조금 더 문제요건을 분석할 줄 알아야 할 것 같다.