[프로그래머스] 표 편집

       문제 요약        

- 문제

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

프로그래머스

 

         아이디어        

- C : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗행을 선택합니다.

- Z : 가장 최근에 삭제된 행을 원래대로 복구합니다.

         소스코드        

- 시간 초과 풀이 

시간 초과가 발생한 이유는 findNextIdx 메서드에서 삭제되지 않은 다음 인덱스를 찾기 위해 모든 행을 순차적으로 탐색하기 때문이다. 많은 행이 삭제된 경우 비효율적이다.

import java.util.*;
class Solution {
    static boolean[] isDeleted;
    public String solution(int n, int k, String[] cmd) {
        isDeleted = new boolean[n];
        Arrays.fill(isDeleted, false);
        
        Stack<Integer> del = new Stack<>();
        int idx = k; // currentId
        for(int i = 0; i < cmd.length; i++) {
            StringTokenizer st = new StringTokenizer(cmd[i]);
            String command = st.nextToken();
            if(command.equals("U")) {
                int X = Integer.parseInt(st.nextToken());
                int nextIdx = findNextIdx(idx, -1, X, n);
                idx = nextIdx;
            } else if(command.equals("D")) {
                int X = Integer.parseInt(st.nextToken());
                int nextIdx = findNextIdx(idx, 1, X, n);
                idx = nextIdx;
            } else if(command.equals("C")) { // 현재 선택된 행을 삭제한 후, 바로 아래 행 선택 만약 마지막 행인 경우 바로 윗행 선택 
                int nextIdx = 0;
                if(isLast(idx, n)) {
                    nextIdx = findNextIdx(idx, -1, 1, n); 
                } else {
                    nextIdx = findNextIdx(idx, 1, 1, n); 
                }
                isDeleted[idx] = true; // 현재 선택된 행 삭제
                del.push(idx); 
                idx = nextIdx;
            } else if(command.equals("Z")) { // 최근에 삭제된 행 복구 
                isDeleted[del.pop()] = false;
            }
        }
        StringBuilder answer = new StringBuilder();
        for(int i = 0; i < n; i++) {
            answer.append(isDeleted[i]?"X":"O");
        }
        
        return answer.toString();
    }
    static boolean isLast(int idx, int n) {
        boolean last = true;
        for(int i = idx + 1; i < n; i++) {
            if(!isDeleted[i]){
                last = false;
                break;
            }
        }
        return last;
    }
    static int findNextIdx(int idx, int way, int dist, int totalSize) {
        int from = idx;
        while(dist > 0) {
            int nextIdx = (from + totalSize + way) % totalSize;
            if(!isDeleted[nextIdx]) {
               dist-= 1;
            }
            from = nextIdx;
        }
        return from;
    }
}

 

- 삭제 여부를 효율적으로 관리할 수 있는 TreeSet을 사용하여 삭제되지 않은 행들만 관리하면

시간 복잡도를 크게 줄일 수 있다.

 

1) 삭제되지 않은 행을 TreeSet으로 관리하기

특정행보다 바로위 lower, higher 의 행을 빠르게 찾을 수 있다

add, remove, higher, lower 등의 작업이 O(logN)에 수행된다

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        TreeSet<Integer> activeRows = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            activeRows.add(i);
        }
        
        Stack<Integer> deletedStack = new Stack<>();
        int current = k;

        for (String command : cmd) {
            char cmdType = command.charAt(0);
            if (cmdType == 'U') {
                int x = Integer.parseInt(command.split(" ")[1]);
                while (x-- > 0) {
                    current = activeRows.lower(current);
                }
            } else if (cmdType == 'D') {
                int x = Integer.parseInt(command.split(" ")[1]);
                while (x-- > 0) {
                    current = activeRows.higher(current);
                }
            } else if (cmdType == 'C') {
                deletedStack.push(current);
                activeRows.remove(current);
                if (activeRows.higher(current) != null) {
                    current = activeRows.higher(current);
                } else {
                    current = activeRows.lower(current);
                }
            } else if (cmdType == 'Z') {
                int restored = deletedStack.pop();
                activeRows.add(restored);
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n; i++) {
            result.append(activeRows.contains(i) ? "O" : "X");
        }
        return result.toString();
    }
}

 

2) 다른 사람 풀이.. 

import java.util.LinkedList;
import java.util.Stack;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Integer> remove_order = new Stack<Integer>();
        int table_size = n;
        for(int i=0; i<cmd.length; i++) {
            char c = cmd[i].charAt(0);
            if(c=='D')
                k+=Integer.parseInt(cmd[i].substring(2));
            else if(c=='U')
                k-=Integer.parseInt(cmd[i].substring(2));
            else if(c=='C') {
                remove_order.add(k);
                table_size--;
                if(k==table_size)
                    k--;
            }
            else if(c=='Z') {
                if(remove_order.pop()<=k)
                    k++;
                table_size++;
            }
        }
        StringBuilder builder = new StringBuilder();
        for(int i=0; i<table_size; i++)
            builder.append("O");
        while(!remove_order.isEmpty())
            builder.insert(remove_order.pop().intValue(), "X");
        String answer=builder.toString();
        return answer;
    }
}