[프로그래머스] 표 편집 - JAVA

문제링크 🚩

 

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

프로그래머스

 

​

📕 문제 접근 📕

 

시간 초과 코드 개선하는 과정이 들어있습니다. 

 

초반 접근 

- 모든 유저는 softdelete가 된다고 생각하였고 이를 배열로만 구현을 하겠다는 생각을 하게 되었음. 

- 삭제된 것을 복귀하기 위한 Stack을 사용하였으며 모든 것들은 배열의 이동을 통해 구현하였음.

결과 : 시간 초과 

원인 : 최대 1,000,000 * 200,000의 연산이 발생할 수 있으며 인덱스의 이동을 통해 구현했기 때문에 다음과 같은 부분에서 시간 초과가 발생하 수 있음.  

현재 유저 인덱스 10 

비활성 유저 인덱스 11 ~ 9999999

다음 활성  유저 인덱스 10000000

다음 인덱스를 찾기 위해 해당 과정을 무수히 반복해야함.  비효율적인 연산이 발생하고 있음을 파악할 수 있음.

 

최적화 접근

- 위와 같은 불 필요한 연산을 최소화하기 위해 양방향 링크드 리스트를 구현.

- 해당 리스트는 활성 유저만을 관리하고 있기 때문에 불 필요한 연산이 필요 없음.

- 비활성 유저의 경우 boolean형 isDel[] 배열을 사용하여 관리함.

- O(N)의 시간에서 인덱스 이동 시 O(1)로 시간을 줄여 효과적인 연산이 가능함. 

 

해당 문제는 del 연산을 어떻게 처리하는지가 중점임

 

 

💻 Code 💻

시간 초과 코드 

import java.util.*;

class Solution {
    static class User {
        int index;
        boolean active;

        public User(int index, boolean active) {
            this.index = index;
            this.active = active;
        }
    }

    static int nowIndex;
    static Stack<Integer> removed = new Stack<>();

    public String solution(int n, int k, String[] cmd) {
        
        nowIndex = k;
        User[] users = new User[n];
        for (int i = 0; i < n; i++) {
            users[i] = new User(i, true);  
        }

        for (String command : cmd) {
            processCommand(command, users);
        }

        return buildResult(users);
    }

    private static void processCommand(String command, User[] users) {
        StringTokenizer st = new StringTokenizer(command);
        String cmd = st.nextToken();

        switch (cmd) {
            case "U":
                moveUp(users, Integer.parseInt(st.nextToken()));
                break;
            case "D":
                moveDown(users, Integer.parseInt(st.nextToken()));
                break;
            case "C":
                delete(users);
                break;
            case "Z":
                undo(users);
                break;
        }
    }


    private static void moveUp(User[] users, int count) {
        int moveCount = 0;
        while (moveCount < count) {
            nowIndex--;
            if (users[nowIndex].active) {
                moveCount++;
            }
        }
    }


    private static void moveDown(User[] users, int count) {
        int moveCount = 0;
        while (moveCount < count) {
            nowIndex++;
            if (users[nowIndex].active) {
                moveCount++;
            }
        }
    }

    private static void delete(User[] users) {
        users[nowIndex].active = false; 
        removed.push(nowIndex); 

        if (isLastActiveRow(users)) {
            moveUp(users, 1); 
        } else {
            moveDown(users, 1); 
        }
    }


    private static boolean isLastActiveRow(User[] users) {
        for (int i = nowIndex + 1; i < users.length; i++) {
           if (users[i].active) {
             return false;  
         }
     }
     return true; 
    }


    private static void undo(User[] users) {
        int restoredIndex = removed.pop();
        users[restoredIndex].active = true; 
    }

    private static String buildResult(User[] users) {
        StringBuilder result = new StringBuilder();
        for (User user : users) {
            if (user.active) {
                result.append("O");
            } else {
                result.append("X");
            }
        }
        return result.toString();
    }
}

 

통과 코드

import java.util.*;

class Solution {
    static class Node{
        int pre;
        int next;
        public Node(int pre, int next){
            this.pre = pre;
            this.next = next;
        }
    }
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        Stack<Integer> delNode = new Stack<>();
        boolean[] isDel = new boolean[n];
        Node[] node = new Node[n]; 
        for(int i = 0; i < n; i++){
            node[i] = new Node(i-1, i +1);
        }
        node[n-1].next = -1; // 마지막 node 처리
        
        int nowIndex = k;
        
        for(String c : cmd){
            char command = c.charAt(0);
            if(command == 'U'){
                int cnt = Integer.parseInt(c.substring(2));
                while(cnt-- > 0) nowIndex = node[nowIndex].pre;
            }else if(command == 'D'){
                int cnt = Integer.parseInt(c.substring(2)); 
                while(cnt-- > 0) nowIndex = node[nowIndex].next;
            }else if(command == 'C'){
                delNode.push(nowIndex);
                isDel[nowIndex] = true;
                if(node[nowIndex].pre != -1) node[node[nowIndex].pre].next = node[nowIndex].next;
                if(node[nowIndex].next != -1) node[node[nowIndex].next].pre = node[nowIndex].pre;
                nowIndex = (node[nowIndex].next == -1) ? node[nowIndex].pre : node[nowIndex].next;
            }else if(command == 'Z'){
                int undoIndex = delNode.pop();
                isDel[undoIndex] = false;
                if(node[undoIndex].pre != -1) node[node[undoIndex].pre].next = undoIndex;
                if(node[undoIndex].next != -1) node[node[undoIndex].next].pre = undoIndex;
                
            }
        }
        
        // 결과 빌드
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (isDel[i]) result.append('X');
            else result.append('O');
        }
        
        return result.toString();
    }
}