[프로그래머스] 표 편집 (2021 카카오 채용연계형 인턴십)

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

2021-09-01

---

import java.util.*;
class Solution {
  static class Node {
        int prev;
        int cur;
        int next;
 
        public Node(int prev, int cur, int next) {
            this.prev = prev;
            this.cur = cur;
            this.next = next;
        }
    }
    static String solution(int n, int k, String[] cmd) {
        int[] prev = new int[n];
        int[] next = new int[n];
 
        for(int i = 0; i < n; i++) { // prev, next init
            prev[i] = i - 1;
            next[i] = i + 1;
        }
 
        next[n-1] = -1; // 마지막 원소 (맨 처음과 끝은 -1 처리)
 
        Stack<Node> stack = new Stack<>(); // remove ) (prev, cur, next)
 
        StringBuilder sb = new StringBuilder("O".repeat(n)); // 초기값
 
        for(int i = 0; i < cmd.length; i++) {
            if(cmd[i].charAt(0) == 'U') {
                int val = Integer.parseInt(cmd[i].substring(2));
                while(val-- > 0) k = prev[k]; // up ) 위로 커서 이동
            } else if(cmd[i].charAt(0) == 'D') {
                int val = Integer.parseInt(cmd[i].substring(2));
                while(val-- > 0) k = next[k]; // down ) 아래로 커서 이동
            } else if(cmd[i].charAt(0) == 'C') {
                stack.push(new Node(prev[k], k , next[k])); // 삭제되는 노드 저장
 
                // 현재 위치가 마지막이 아닌 경우
                if(next[k] != -1) prev[next[k]] = prev[k];
                // 현재 위치가 처음이 아닌 경우
                if(prev[k] != -1) next[prev[k]] = next[k];
 
                //삭제 처리
                sb.setCharAt(k, 'X');
 
                // 마지막이 아닌 경우
                if(next[k] != -1) k = next[k];
                else k = prev[k];
            } else { // Z
                int pre = stack.peek().prev;
                int cur = stack.peek().cur;
                int nxt = stack.peek().next;
 
                // prev, next는 이미 변경 됐으므로
                if(nxt != -1) prev[nxt] = cur;
                if(pre != -1) next[pre] = cur;
 
                sb.setCharAt(cur, 'O');
                stack.pop();
            }
        }
 
        return sb.toString();
    }
}

#문제풀이

링크드리스트, 스택을 써야하는 컨셉은 잡았는데 Z부분에 대한 처리 등 디테일한 구현 부분의 컨셉을 못 잡았어서, 아래 블로그를 참고해서 풀었다. 

https://blog.encrypted.gg/1001?category=916869 

[2021 카카오 채용연계형 인턴십] Q3. 표 편집 (C++, Python, Java)

 

1) 연결리스트 노드는 prev, cur, next 3가지를 관리할 수 있도록 만든다. 

2) 그리고 원소들의 index를 따로 관리할 수 있게 prev배열과 next배열을 만든다. 초기값 세팅 시, 맨 앞 노드의 prev는 -1이 되고 맨 뒤 노드의 next는 -1로 처리한다.

 

3) 'U', 'D'는 k값만 움직이면 되니깐, 딱히 처리해야할 부분은 없다. 

 

4) 'C'는 현재 위치의 값을 삭제 해야한다. 이 때, 연결된 부분들을 처리 해줘야한다. 

예를 들어, 아래와 같은 경우에서 가운데(k == 1)를 삭제해야하는 경우가 있다면, 삭제해야할 노드 값을 stack에 (prev, cur, next)를 넣으면 된다. 

삭제 전 초기 세팅은 아래와 같을 것이다.

그리고 삭제 시, 현재 위치가 마지막이 아닌 경우와 현재 위치가 처음이 아닌 경우를 체크하고 prev와 next 배열 값을 업데이트 해준다.

그리고 StringBuilder에서 해당 위치를 삭제 처리 해준다. 마지막으로, 문제 조건에 따라 삭제된 노드가 맨 마지막인지 아닌지에 따라 k값을 업데이트 해줘야한다. 

 

5) 'Z'는 stack에 넣어놨던 값을 꺼내서 복구해주면 된다.

stack에서 pop을 해서 삭제 되었던 prev, cur, next를 꺼낼 수 있다. 그래서 가장 처음 노드, 가장 마지막 노드인 경우를 체크하면서 prev배열과 next배열을 복구하면 된다. 그리고 StringBuilder에서 해당 위치 삭제처리했던 것을 복구시킨다.