[프로그래머스] [Java] 표 편집

문제 설명

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

프로그래머스

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다.

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

처음 코드

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        
        //배열 만들기
        int[] state = new int[n];
        Arrays.fill(state,1);
        int cur_deleted = 0;
        
        for (String c : cmd) {
            String[] parts = c.split(" ");
            String command = parts[0];
            int value = 0;
            if (parts.length > 1) {
                value = Integer.parseInt(parts[1]);
            }
            switch(command) {
                case "U":
                    k -= value;
                    break;
                case "D":
                    k += value;
                    break;
                case "C":
                    state[k] = 0;
                    cur_deleted = k;
                    if (k == n-1) k-=1;
                    else k += 1;
                    break;
                case "Z":
                    state[cur_deleted] = 1;
                    break;
            }
        }
        return answer;
    }
}

state 배열로 삭제 여부를 0, 1로 표현했다.

하지만 선택된 행(k)이 삭제된 상태에서 위/아래로 이동할 때나 Z를 복구할 때 문제가 발생할 수 있다.

문제점

1. 삭제한 행은 다시 선택할 수 없어야 하는데, 단순히 k++ 또는 k--로 이동하면 삭제된 행을 선택하게 됨
2. Z 복구는 cur_deleted 하나만 저장해서, 복수의 삭제를 복구할 수 없음

개선 방향

1. 삭제한 행을 스택에 저장

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

2. 위/아래 이동 시 삭제된 행 건너뛰기

// 위로
while (value > 0) {
    k--;
    if (state[k] == 1) value--;
}

// 아래로
while (value > 0) {
    k++;
    if (state[k] == 1) value--;
}

최종 코드

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        int[] state = new int[n];
        Arrays.fill(state, 1);  // 1 = 존재, 0 = 삭제
        Stack<Integer> deleted = new Stack<>();

        for (String c : cmd) {
            String[] parts = c.split(" ");
            String command = parts[0];
            int value = parts.length > 1 ? Integer.parseInt(parts[1]) : 0;

            switch (command) {
                case "U":
                    while (value > 0) {
                        k--;
                        if (state[k] == 1) value--;
                    }
                    break;

                case "D":
                    while (value > 0) {
                        k++;
                        if (state[k] == 1) value--;
                    }
                    break;

                case "C":
                    state[k] = 0;
                    deleted.push(k);

                    // 아래쪽 존재하는 행 찾기
                    int temp = k + 1;
                    while (temp < n && state[temp] == 0) temp++;
                    if (temp < n) {
                        k = temp;
                    } else {
                        // 위쪽 존재하는 행
                        temp = k - 1;
                        while (temp >= 0 && state[temp] == 0) temp--;
                        k = temp;
                    }
                    break;

                case "Z":
                    if (!deleted.isEmpty()) {
                        int recover = deleted.pop();
                        state[recover] = 1;
                    }
                    break;
            }
        }

        // 최종 결과 문자열 만들기
        StringBuilder sb = new StringBuilder();
        for (int s : state) {
            sb.append(s == 1 ? 'O' : 'X');
        }
        return sb.toString();
    }
}