[프로그래머스] 표 편집 - 81303 (Java)

문제 URL

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

나의 코드

import java.util.Arrays;
import java.util.Stack;

public class Solution {

    public String solution(int n, int k, String[] cmd) {
        Stack<Integer> deleted = new Stack<>();

        // 배열 크기를 n으로 설정하고 초과 인덱스 처리
        int[] up = new int[n];
        int[] down = new int[n];

        // 초기 연결 리스트 관계 설정
        for (int i = 0; i < n; i++) {
            up[i] = i - 1;
            down[i] = i + 1;
        }

        // 현재 위치를 설정
        int current = k;

        for (String command : cmd) {
            char operation = command.charAt(0);

            if (operation == 'C') {
                // 현재 행 삭제
                deleted.push(current);

                // 연결 관계 수정
                if (up[current] != -1) down[up[current]] = down[current];
                if (down[current] != n) up[down[current]] = up[current];

                // 다음 위치로 이동
                current = (down[current] == n) ? up[current] : down[current];
            } else if (operation == 'Z') {
                // 복원
                int restore = deleted.pop();

                // 연결 관계 복구
                if (up[restore] != -1) down[up[restore]] = restore;
                if (down[restore] != n) up[down[restore]] = restore;
            } else {
                // U 또는 D 명령어 처리
                int x = Integer.parseInt(command.substring(2));
                for (int i = 0; i < x; i++) {
                    current = (operation == 'U') ? up[current] : down[current];
                }
            }
        }

        // 결과 배열 생성
        char[] result = new char[n];
        Arrays.fill(result, 'O');
        while (!deleted.isEmpty()) {
            result[deleted.pop()] = 'X';
        }

        return new String(result);
    }
}

---

해결 방법

1. 배열을 이용한 연결 리스트 구현

배열을 이용하여 각 행의 위와 아래 연결 관계를 저장합니다. 이를 통해 삭제 및 복원 작업을 효율적으로 처리할 수 있습니다.

• up[i]: 행 i의 위쪽 행의 인덱스를 저장.
• down[i]: 행 i의 아래쪽 행의 인덱스를 저장.

초기 설정에서는 모든 행이 연결되어 있으므로:

• up[i] = i - 1 (i가 0인 경우는 -1, 즉 위에 행이 없다)
• down[i] = i + 1 (i가 마지막 행인 경우는 n, 즉 아래에 행이 없다)

2. 삭제된 행을 위한 스택 사용

삭제된 행은 복원할 수 있도록 스택에 저장합니다. C 명령어가 수행되면 해당 행을 삭제하고, 삭제된 행은 스택에 푸시됩니다. 이후 Z 명령어가 수행되면 스택에서 꺼내어 복원할 수 있습니다.

3. 명령어 처리

1) C 명령어 (현재 행 삭제)

현재 행을 삭제하려면, 해당 행을 삭제하고 위아래 연결을 수정합니다.

• 삭제 후 연결 수정:
  • 현재 행의 위쪽 행과 아래쪽 행을 서로 연결시킵니다.
  • up[down[current]] = up[current]
  • down[up[current]] = down[current]
• 현재 위치 갱신:
  • 삭제 후 이동할 위치를 결정합니다. 만약 아래쪽 행이 존재하면 그곳으로 이동하고, 그렇지 않으면 위쪽 행으로 이동합니다.

2) Z 명령어 (삭제된 행 복원)

삭제된 행을 복원하려면, 스택에서 최근에 삭제된 행을 꺼내고 연결을 복구합니다.

• 복원 후 연결 복구:
  • 복원된 행의 위와 아래 행의 연결을 다시 설정합니다.
  • down[up[restore]] = restore
  • up[down[restore]] = restore

3) U와 D 명령어 (위/아래로 이동)

U x는 현재 위치에서 위로 x만큼 이동하고, D x는 아래로 x만큼 이동하는 명령어입니다. 각 명령어에 대해 current 인덱스를 적절히 갱신합니다.

문제해결 포인트

처음에는 배열을 그대로 활용하여 시간 초과 문제가 발생했습니다. 문제는 배열에서 삭제된 행을 처리할 때, 연결을 수정하는 데 시간이 오래 걸린다는 점이었습니다. 이를 해결하기 위해 배열을 활용한 연결 리스트 구현으로 성능을 최적화할 수 있었습니다.

연결 리스트처럼 배열을 활용하여 각 행의 위와 아래 연결 관계를 관리하는 방식으로 삭제, 복원, 이동을 효율적으로 처리했습니다. 이 방식으로 O(1) 시간 내에 행의 삭제와 복원이 가능해졌습니다.

결과적으로, 배열을 그대로 사용한 방법에서 발생한 시간 초과 문제를 연결 리스트의 아이디어를 배열로 구현하는 방식으로 해결하며 문제를 효율적으로 풀 수 있었습니다.