[프로그래머스] Lv.3 표 편집

알고리즘 : 스택 + 배열로 구현한 리스트

문제 설명

링크 참조

 

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

프로그래머스

 

 

---

기존 풀이

처음 문제를 보자마자 나는 change라는 삭제되었는지 안되었는지를 표시하는 배열을 선언하고
인덱스만 이리저리 움직이면서 stack을 활용해서 풀 수 있을줄 알았다.
하지만 최종 코드를 작성하고 답을 제출하니 정확성 테스트 통과 및 일부 효율성 테스트 통과 했다.
시간초과도 발생하였고, 잘못된 알고리즘으로 코드를 작성했음을 깨달았다.

배열은 삽입과 삭제시 원하는 위치까지 탐색을 진행 후 수행하기에 비효율적이다.
또한 U,D 움직임 경우에 항상 다음 위치의 change값을 확인하므로 시간효율적이지 못하다.

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        int[] change = new int[n];
        int current = k;
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (String command : cmd) {
            String[] parts = command.split(" ");
            String inst = parts[0];

            if (inst.equals("D")) {
                int offset = Integer.parseInt(parts[1]);
                for (int i = 0; i < offset; ) {
                    current++;
                    if (change[current] != 1) {
                        i++;
                    }
                }
            } 
            else if (inst.equals("U")) {
                int offset = Integer.parseInt(parts[1]);
                for (int i = 0; i < offset; ) {
                    current--;
                    if (change[current] != 1) {
                        i++;
                    }
                }
            } 
            else if (inst.equals("C")) {
                stack.push(current);
                change[current] = 1;

                // 아래 행으로 이동, 마지막 행이면 위로 이동
                boolean moved = false;
                for (int i = current + 1; i < n; i++) {
                    if (change[i] == 0) {
                        current = i;
                        moved = true;
                        break;
                    }
                }
                if (!moved) {
                    for (int i = current - 1; i >= 0; i--) {
                        if (change[i] == 0) {
                            current = i;
                            break;
                        }
                    }
                }
            } 
            else if (inst.equals("Z")) {
                int restoredIndex = stack.pop();
                change[restoredIndex] = 0;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (change[i] == 1) sb.append("X");
            else sb.append("O");
        }

        return sb.toString();
    }
}

---

올바른 풀이

그러면 배열을 사용하지말고 리스트를 쓰면되나? -> 연결 리스트 처럼
여기서 핵심은 인덱스만 사용해서 연산을 수행하는 것이다.
시간 효율적으로 구현하자.
연결 리스트를 배열 2개를 통해 구현했다.

기조는 up,down 배열을 만들어 해당 인덱스의 up,down 인덱스 값을 저장하고, 움직이거나 삭제, 복구 시 바로 up,down 배열로 작업을 수행

1. N+2 크기의 up,down 배열을 선언한다.

• N으로 선언 시 양쪽 끝의 삭제 과정에 Out of Index 에러 발생

위 그림 처럼 삭제 과정에서 out of index 발생하기에 N+2로 선언
2. current 값을 1 증가 ( N + 2에 맞춤 )
3. 명령어 길이 만큼 반복문 수행

• U,D의 경우는 X의 크기 만큼 current 값을 증가 시켜야된다. 말했다시피 여기서 시간 초과가 발생했던 것 같다.
• 이 부분을 생각 해야 될 부분은 x 만큼 이동 할 때 U, D에 맞게 up,down 배열로 수행하면 된다. x만큼을 초과하지 않는 연산을 수행하는 것
• C는 생각을 해보면, 현재 노드가 삭제되면 up노드의 down과 down 노드의 up이 바뀌어야 됨을 알 수 있다.
• 또한 삭제 이므로 deleted 스택에 인덱스를 추가하자!
• Z는 deleted 스택에서 pop해서, 해당 인덱스의 up노드의 down과 down 노드의 up을 바꿔준다.

4. 마지막으로 deleted 스택에 존재하는 인덱스 값만 x로 바꿔서 수행

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        int[] up = new int [n+2];
        int[] down = new int [n+2];

        // 리스트 초기화 
        for (int i =0;i < n+2;i++){
            up[i] = i -1;
            down[i] = i+1;
        }
        int current = k+1;

        ArrayDeque<Integer> deleted = new ArrayDeque<>();

        for (String s : cmd){
            if (s.startsWith("C")){
                deleted.push(current);
                down[up[current]] = down[current];
                up[down[current]] = up[current];
                current = n < down[current] ? up[current] : down[current];
            }
            else if (s.startsWith("Z")){
                int temp = deleted.pop();
                down[up[temp]] = temp;
                up[down[temp]] = temp;
            }
            else {
                String[] sp = s.split(" ");
                int offset = Integer.parseInt(sp[1]);

                for (int i = 0 ; i < offset; i++){
                    current = sp[0].equals("U") ? up[current] : down[current];
                }
            }
        }
        char[] answer = new char[n];
        Arrays.fill(answer,'O');

        for (int i : deleted) {
            answer[i-1] = 'X';
        }


        return new String(answer);
    }
}