(프로그래머스) 표 편집

문제

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

풀이

인덱스만 좀 조심해서 구현하면 되는 문제같다. 처음에 단순히 ArrayList를 사용하여 풀어서 정확성 측면에서는 통과했지만, 효율성 측면에서는 통과하지 못했다. 우선 처음에 작성한 코드는 다음과 같다.

코드 1

import java.util.*;

// 스택에서 보관할 노드
class Node {
    int originalIndex;
    int newIndex;
    
    Node (int originalIndex, int newIndex) {
        this.originalIndex = originalIndex;
        this.newIndex = newIndex;
    }
}

class Solution {
    public String solution(int n, int k, String[] cmd) {
        boolean[] deleted = new boolean[n]; // 삭제 여부
        Stack<Node> stack = new Stack<>(); 
        List<Integer> list = new ArrayList<>();
        int idx = k;
        
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        
        for (int i = 0; i < cmd.length; i++) {
            String str = cmd[i];
            char c = str.charAt(0);
            
            if (c == 'D') {
                // 아래로 이동
                int v = Integer.parseInt(str.split(" ")[1]);
                idx += v;
            } else if (c == 'C') {
                int originalIndex = list.get(idx);
                stack.push(new Node(originalIndex, idx));
                list.remove(idx);
                deleted[originalIndex] = true;
                
                if (idx == list.size()) {
                    idx--;
                }
            } else if (c == 'U') {
                // 위로 이동
                int v = Integer.parseInt(str.split(" ")[1]);
                idx -= v;
            } else {
                // c == 'Z'
                Node node = stack.pop();
                list.add(node.newIndex, node.originalIndex);
                deleted[node.originalIndex] = false;
                
                if (node.newIndex <= idx) {
                    idx++;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < deleted.length; i++) {
            if (deleted[i]) {
                sb.append("X");
            } else {
                sb.append("O");
            }
        }
        
        return sb.toString();
    }
}

list.remove나 list.add(index, Object) 하는 과정에서 시간초과가 난 것으로 측정된다. 생각해보니 이들이 라이브러리로서 Array의 크기를 신경쓰지 않고 구현할 수 있도록 돕는 것이지, 시간복잡도를 O(1)로 줄여주는 녀석들은 아니었기 때문이다.

중간 원소 삽입이나 삭제를 구현할 때 LinkedList를 이용하면 O(1)로 해결이 가능하겠지만, 문제가 중간 원소에 O(1)로 접근할 수 없는 LinkedList의 성격과 맞지 않는다.

따라서 본인의 바로 앞 숫자와 바로 뒤 숫자를 저장하는 배열을 따로 두어 구현 하는 방법으로 진행하게 되었다.

코드 2

import java.util.*;

class Node {
    int prev;
    int cur;
    int next;
    
    Node (int prev, int cur, int next) {
        this.prev = prev;
        this.cur = cur;
        this.next = next;
    }
}

class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Node> stack = new Stack<>();
        StringBuilder sb = new StringBuilder("O".repeat(n));
        
        int idx = k;
        int[] prev = new int[n];
        int[] next = new int[n];
        
        for (int i = 0; i < n; i++) {
            prev[i] = i - 1;
            next[i] = i + 1;
        }
        
        prev[0] = -1;
        next[n - 1] = -1;
        
        for (int i = 0; i < cmd.length; i++) {
            String str = cmd[i];
            char c = str.charAt(0);
            
            if (c == 'U') {
                int cnt = Integer.parseInt(str.split(" ")[1]);
                while (cnt > 0) {
                    idx = prev[idx];
                    cnt--;
                }
            } else if (c == 'D') {
                int cnt = Integer.parseInt(str.split(" ")[1]);
                while (cnt > 0) {
                    idx = next[idx];
                    cnt--;
                }
            } else if (c == 'C') {
                stack.push(new Node(prev[idx], idx, next[idx])); 
                sb.setCharAt(idx, 'X');
                
                if (prev[idx] != -1) {
                    next[prev[idx]] = next[idx];
                }
                
                if (next[idx] != -1) {
                    prev[next[idx]] = prev[idx];
                } 
                
                if (next[idx] != -1) {
                    idx = next[idx];
                } else {
                    idx = prev[idx];
                }
            } else {
                // c == 'Z'
                Node node = stack.pop();
                sb.setCharAt(node.cur, 'O');
                
                if (node.prev != -1) {
                    next[node.prev] = node.cur;
                }
                
                if (node.next != -1) {
                    prev[node.next] = node.cur;
                }
            }
        }
        
        return sb.toString();
    }
}