[프로그래머스] 표 편집

1. 문제

---

프로그래머스

2. 풀이 과정

---

사악한 입력크기를 보니 효율성을 엄청 따져야 할 것 같은 문제라는 생각이 들었다. 게다가 이문제는 레벨3문제...

일단 저 표의 상태를 어떻게 저장할지를 고민했다.

 

그래도 일단 쉽게 생각했다.

• N 크기의 배열을 만들어 데이터가 있으면 True, 없으면 False
• 데이터가 삭제되면 True --> False
• 데이터가 복구되면 False --> True
• 삭제된 데이터를 저장할 저장소는 복구시 가장 최근의 삭제된 데이터를 불어와야 하므로  스택
• 모든 명령어를 다 끝낸 뒤 그 배열을 보고 True이면 O, False이면 F를 반환

이제 그림으로 보자

n:8 , k:2, cmd:  ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] 

 

0. 초기 상태

 

1. D 2

2. C

• 여기서 주의해야할 부분은 삭제 시 Cursor을 아래로 1 내려줘야 한다는 점이다.

3. U 3

• 여기서 주의해야할 부분은 5에서 위로 3칸 가면 2일것 같지만 4에 지금 데이터가 없으므로 이는 무시하고 움직여야 한다.

4. C

5. D 4

6. C

• 여기서 주의해야할 점은 7은 마지막 행이므로 삭제하게 되면 커서를 위로 한칸 올려줘야 한다.

7. U 2

8. Z

• 복구시에는 스택에서 하나 꺼내 해당 행을 다시 True로 만든다.
• 여기서 주의해야할 점은 복구시 커서는 변경되지 않는다.

9. Z

 

스택에는 4만이 남아있으므로 최종적으로 답은 "OOOOXOOO"가 된다.

 

이제 이를 구현해보자

3. 내 코드

---

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
       
        int cursor = k; // 현재 선택된 행
        int last_row = n - 1;
        boolean[] table = new boolean[n]; // 표
        Stack<Integer> delete_row = new Stack<>(); // 삭제 행 번호
        
        Arrays.fill(table, true);
        
        // 명령어 수행
        for(String s: cmd) {
            char c = s.charAt(0);
            if(c == 'U') {
                int move = Integer.parseInt(s.substring(2));
                cursor = upCursor(table, cursor, move);
            } else if(c == 'D') {
                int move = Integer.parseInt(s.substring(2));
                cursor = downCursor(table, cursor, move);
            } else if(c == 'C') {
                delete_row.push(cursor);
                table[cursor] = false;
                if(cursor == last_row) { // 삭제한 행의 위치가 마지막 행인 경우 
                    last_row--;
                    cursor = upCursor(table, cursor, 1);
                } else {
                    cursor = downCursor(table, cursor, 1);
                }
            } else if(c == 'Z') {
                int refresh_row = delete_row.pop();
                table[refresh_row] = true;
                if(refresh_row == last_row + 1) { // 복구된 행의 위치가 마지막 행보다 아래인 경우
                    last_row++;
                }
            }
        }
        
        StringBuilder answer = new StringBuilder();

        
        for(boolean haveData : table) {
            // 표에 데이터가 있으면 O, 없으면 그대로 X
            if(haveData) {
                answer.append("O");
            } else {
                answer.append("X");
            }
        }
        
        
        return answer.toString();
    }
    
    private int upCursor(boolean[] table, int cursor, int move) {
        while(move > 0) {
                cursor--;
                if(table[cursor]) {
                    move--;
                }
            }
        return cursor;
    }
    
    private int downCursor(boolean[] table, int cursor, int move) {
        while(move > 0) {
                cursor++;
                if(table[cursor]) {
                    move--;
                }
            }
        
        return cursor;
    }
}

시간복잡도

• O(N^2)

채점 결과

 

정확성은 만족했지만 효율성은 만족하지 못했다...

입력크기와 시간복잡도를 고려하면 당연한 결과...

 

시간복잡도를 늘린부분은 다음일 것이다. 

private int upCursor(boolean[] table, int cursor, int move) {
        while(move > 0) {
                cursor--;
                if(table[cursor]) {
                    move--;
                }
            }
        return cursor;
    }
    
private int downCursor(boolean[] table, int cursor, int move) {
    while(move > 0) {
            cursor++;
            if(table[cursor]) {
                move--;
            }
        }

    return cursor;
}

• 커서를 움직이는 부분
  • 커서를 움직일 때 해당 데이터가 있는지 없는지를 따져야 했기 때문에 시간이 오래걸렸다.

 

그래서 이런거 따질필요도 없이 리스트를 사용해서 실제로 데이터를 삽입하고 삭제하는 방식으로도 구현해봤었다.

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
       
        int cursor = k; // 현재 선택된 행
        ArrayList<Integer> table = new ArrayList<>(); // 표
        Stack<Integer> delete_row = new Stack<>(); // 삭제 행 번호
        Stack<Integer> delete_data = new Stack<>(); // 삭제 데이터
        
        for(int i = 0; i < n; i++) {
            table.add(i); // 행 번호를 표에 저장 
        }
        
        // 명령어 수행
        for(String s: cmd) {
            char c = s.charAt(0);
            if(c == 'U') {
                cursor -= Integer.parseInt(s.substring(2));
            } else if(c == 'D') {
                cursor += Integer.parseInt(s.substring(2));
            } else if(c == 'C') {
                delete_row.push(cursor);
                delete_data.push(table.get(cursor));
                table.remove(cursor);
                if(cursor == table.size()) { // 삭제한 행의 위치가 마지막 행인 경우 
                    cursor--;
                }
            } else if(c == 'Z') {
                int row = delete_row.pop();
                int data = delete_data.pop();
                table.add(row, data);
                if(row <= cursor) { // 복구된 데이터의 행이 현재 커서 위치보다 더 위일 경우
                    cursor++;
                }   
            }
        }
        
        StringBuilder answer = new StringBuilder();
        
        for(int i = 0; i < n; i++) {
            answer.append("X"); // 정답 문자열 초기화
        }
        
        for(int row : table) {
            // 표에 데이터가 있으면 O, 없으면 그대로 X
            answer.setCharAt(row, 'O');
        }
        
        
        return answer.toString();
    }
}

시간복잡도

• O(N^2)

채점 결과

결과가 더 안좋아졌다.

table.remove(cursor);

table.add(row, data);

• ArrayList에서 특정 인덱스 중간에 데이터를 삽입하고 특정 인덱스의 데이터를 삭제하는 작업은 생각보다 오래걸린다.

 

4. 다른 정답 코드와 비교

---

[프로그래머스 정답코드]

import java.util.Stack;

class Solution {

    Stack<Node> stack;

    public class Node {

        int data;
        Node prev, next;

        public Node() {

        }

        public Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }

        public Node remove() {
            prev.next = next;
            next.prev = prev;
            if (this.next.data == -1) { // 마지막 노드인 경우 -> 삭제시 이전 노드로
                return this.prev;
            } else {
                return this.next;
            }
        }

        public void restore() { // 재연결
            prev.next = this;
            next.prev = this;
        }
    }

    public Node init(int n) {
        Node initNode = new Node(-1); // 시작 노드
        Node prevNode = initNode;
        Node curNode = null;

        for (int i = 0; i < n; i++) {
            curNode = new Node(i);
            prevNode.next = curNode;
            curNode.prev = prevNode;

            prevNode = curNode;
        }

        Node endNode = new Node(-1);
        curNode.next = endNode;
        return initNode.next;
    }

    public String solution(int n, int k, String[] cmd) {
        Node cursor = init(n);
        stack = new Stack<>();
        for (int i = 0; i < k; i++) { // 시작 커서 이동
            cursor = cursor.next;
        }

        for (int i = 0; i < cmd.length; i++) {
            String[] command = cmd[i].split(" ");
            String op = command[0];

            if ("U".equals(op)) {
                int opNum = Integer.parseInt(command[1]);
                cursor = up(cursor, opNum);
            } else if ("D".equals(op)) {
                int opNum = Integer.parseInt(command[1]);
                cursor = down(cursor, opNum);
            } else if ("C".equals(op)) {
                cursor = delete(cursor);
            } else { // 복구
                restore();
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append("O");
        }

        while (!stack.isEmpty()) {
            sb.setCharAt(stack.pop().data, 'X');
        }

        return sb.toString();
    }

    Node up(Node cur, int num) {
        for (int i = 0; i < num; i++) {
            cur = cur.prev;
        }

        return cur;
    }

    Node down(Node cur, int num) {
        for (int i = 0; i < num; i++) {
            cur = cur.next;
        }

        return cur;
    }

    Node delete(Node cur) {
        stack.push(cur);
        cur = cur.remove();
        return cur;
    }

    void restore() {
        Node dNode = stack.pop();
        dNode.restore();
    }
}

시간복잡도

• O(N)

설명

답은 Doubly LinkedList(양방향 링크드 리스트)였다. 

Doubly LinkedList를 사용하게 되면 삭제, 삽입 시 처리를 효율적으로 할 수 있다. 

Doubly LinkedList는 현재 노드에서 이전 노드와 다음 노드를 참조하고 있다. 

 

삭제시

ex: Node(2) 삭제

• Node1의 다음 노드, Node3의 이전 노드에 대한 참조만 바꿔주면 된다
• 이러한 과정은 O(1)로 수행된다. 

삽입시

• 삽입시에도 Node1의 다음노드, Node3의 이전 노드에 대한 참조만 다시 원래대로 바꿔주면 된다
• 이러한 과정은 O(1)로 수행된다.

 

5. 피드백

---

• 연속적인 데이터에 데이터를 특정부분에 삽입하거나 특정 부분의 데이터를 삭제할 때는 Doubly LinkedList가 매우 효율적이다.
  • 그냥 삽입, 삭제하고 이전, 다음 노드에 대한 참조만 바꿔주면 됨.
• 최근 데이터를 참조하기 위해서는 스택 자료구조가 제일 효율적이다.

 

Doubly LinkedList 참고

자바 [JAVA] - Doubly LinkedList (이중 연결리스트) 구현하기