Today I Learned

오늘은 주말에 있을 K사 코테를 대비해 코테를 간만에 풀었다. 간만이라 그런지 발상은 쉬웠으나 구현에 좀 애를 먹었다.

표 편집

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

문제

위와 같은 테이블이 주어지고, 파란색 칸은 현재 선택된 행을 뜻한다.
파란 칸은 표의 범위(0~마지막행)을 벗어날 수 없고 다음과 같은 명령어로 표를 편집한다

"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
"D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
"C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
"Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

처음 표의 행 개수 n, 처음 선택된 행의 위치 k, 명령어가 담긴 문자열 배열 cmd가 주어질 때, 모든 명령어 수행 후 처음 표와 비교해 삭제된행은 X, 삭제 안된 행은 O로 표시해 문자열로 return해라.

풀이과정

• 우선 양방향 연결리스트를 직접 구현해 풀면 적합하겠다는 생각을 바로 떠올렸다.

• 각 행이 Node가 되고, Node안에는 삭제여부 boolean값, 이전 노드, 다음 노드의 정보가 있으면 된다.

1. Node 클래스를 구현한다.

2. Node를 담을 배열을 만들고 반복문으로 안의 Node들을 만들고 이전과 다음 Node로 연결시켜 초기화 해준다.

3. 현재 노드, 이전, 다음노드, 변수 tmp, 노드 부활을 위한 스택을 생성한다.

4. 반복문으로 cmd배열을 열어 string값의 첫 글자를 기준으로 switch-case문을 만든다.

4-1. U가 나올경우 현재노드만 위로 X번 가면 되니, 반복문으로 now = now.prev;을 돌려 타고 올라가게 해준다.
4-2. D가 나올경우 현재노드만 아래로 X번 가면 되니, 반복문으로 now = now.next;를 돌려 타고 내려가게 해준다.
4-3. C가 나올경우 현재 노드의 deleted를 true로 바꾸고 스택에 넣는다.
그리고 이전노드가 있으면 그 노드의 다음노드를 현재 노드의 다음노드로 연결시켜주고, 다음노드도 반대로 똑같이 해준다. 단, 현재노드의 다음노드는 없으면 현재 노드를 바로 위 노드로 올린다.
4-4. 스택에 저장해둔 노드를 부활시킨다. deleted를 false로 다시 바꾸고, 이전노드의 다음노드와 다음노드의 이전노드를 부활시킨 노드로 바꿔준다.

5. StringBuilder로 노드배열의 deleted값에 따라 X와 O를 넣어주고 String으로 다시 바꿔서 return하면 해결!

Java 코드

import java.util.*;
class Solution {
        
    class Node {
        boolean deleted;
        Node prev;
        Node next;
        
    }
    
    public String solution(int n, int k, String[] cmd) {
        
        Node[] nodes = new Node[n];
        Deque<Node> stack = new ArrayDeque<>();
        
        
        for(int i=0; i<n; i++){
            nodes[i] = new Node();
        }
        for(int i=1; i<n; i++){
            nodes[i].prev = nodes[i-1];
            nodes[i-1].next = nodes[i];
        }
        
        Node now = nodes[k];
        Node up;
        Node down;
        int tmp;
        
        for(String str : cmd){
            char c = str.charAt(0);
            switch(c) {
                case 'U' :
                    tmp = Integer.parseInt(str.substring(2));
                    for(int i=0; i<tmp; i++){
                        now = now.prev;
                    }
                    break;
                case 'D' :
                    tmp = Integer.parseInt(str.substring(2));
                    for(int i=0; i<tmp; i++){
                        now = now.next;
                    }
                    break;
                case 'C' :
                    now.deleted = true;
                    stack.push(now);
                    up = now.prev;
                    down = now.next;
                    
                    if(up != null){
                        up.next = down;
                    }
                    
                    if(down != null){
                        down.prev = up;
                        now = down;
                    } else {
                        now = up;
                    }
                    break;
                case 'Z' :
                    Node rev = stack.pop();
                    up = rev.prev;
                    down = rev.next;
                    
                    rev.deleted = false;
                    if(up != null){
                        up.next = rev;
                    }
                    if(down != null){
                        down.prev = rev;
                    }
                    break;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<n; i++){
            if(nodes[i].deleted){
                sb.append("X");
            } else {
                sb.append("O");
            }
        }
        
        return sb.toString();
    }
    
}