[Java] Lv2. 표 편집

🔗 문제 링크

프로그래머스

 

 

📝 문제 설명

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

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

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

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

 

⚠️ 제한 사항

• 5 ≤ n ≤ 1,000,000
• 0 ≤ k < n
• 1 ≤ cmd의 원소 개수 ≤ 200,000
  • cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
  • X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.
  • X가 나타내는 자연수에 ',' 는 주어지지 않습니다. 예를 들어 123,456의 경우 123456으로 주어집니다.
  • cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
  • 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
  • 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 "이름" 열을 사용하였으나, "이름"열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요.
• 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
• 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없습니다.
• 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.

정확성 테스트 케이스 제한 사항

• 5 ≤ n ≤ 1,000
• 1 ≤ cmd의 원소 개수 ≤ 1,000

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

 

✨ 내 코드

최종 코드 (책 참고)

class Solution {
    public String solution(int n, int k, String[] cmd) {
        int[] prev = new int[n + 2];
        int[] after = new int[n + 2];
        for (int i = 0; i < n + 2; i++) {
            prev[i] = i - 1; //[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
            after[i] = i + 1; //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        }

        int current = k + 1;

        Stack<Integer> deleted = new Stack<>();
        for(String c : cmd) {
            if (c.equals("C")) {
                deleted.push(current);
                prev[after[current]] = prev[current];
                after[prev[current]] = after[current];

                current = n < after[current] ? prev[current] : after[current];

            } else if (c.equals("Z")) {
                int restore = deleted.pop();
                prev[after[restore]] = restore;
                after[prev[restore]] = restore;

            } else {
                String[] split = c.split(" ");
                int movement = Integer.parseInt(split[1]);

                for(int i = 0; i < movement; i++) {
                    current = split[0].equals("U") ? prev[current] : after[current];
                }
            }
        }

        char[] answer = new char[n];
        Arrays.fill(answer, 'O');

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

        return new String(answer);
    }
}

첫 코드

런타임 에러 및 시간 초과 발생

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

class Solution {
    public String solution(int n, int k, String[] cmd) {
        // 상태 체크용 배열("O"으로 초기화)
        String[] tableStatus = new String[n];
        for(int i = 0; i < n; i++) {
            tableStatus[i] = "O";
        }

        // 시작 인덱스 초기화
        int currentIdx = k;

        // 삭제된 인덱스 저장용 배열
        Stack<Integer> deleted = new Stack<>();
        for(int i = 0; i < cmd.length; i++) {
            if (cmd[i].contains("U")) {
                String[] splitCmd = cmd[i].split(" ");
                int movement = Integer.parseInt(splitCmd[1]);

                // X는 건너뛰고 앞으로
                int count = 0;
                while (count != movement) {
                    if (tableStatus[currentIdx - 1] == "O") {
                        count++;
                    }
                    currentIdx--;
                }

            } else if (cmd[i].contains("D")) {
                String[] splitCmd = cmd[i].split(" ");
                int movement = Integer.parseInt(splitCmd[1]);

                // X는 건너뛰고 뒤로
                int count = 0;
                while (count != movement) {
                    if (tableStatus[currentIdx + 1] == "O") {
                        count++;
                    }
                    currentIdx++;
                }

            } else if (cmd[i].equals("C")) {
                // 스택에 삭제된 인덱스 push 후 값 X로 변경
                deleted.push(currentIdx);
                tableStatus[currentIdx] = "X";

                if (currentIdx == n - 1) { // 마지막 인덱스면 뒤로 가지말고 앞으로 한 칸(X는 건너뛰고)
                    int count = 0;
                    while (count != 1) {
                        if (tableStatus[currentIdx - 1] == "O") {
                            count++;
                        }
                        currentIdx--;
                    }

                } else { // X는 건너뛰고 뒤로
                    int count = 0;
                    while (count != 1) {
                        if (tableStatus[currentIdx + 1] == "O") {
                            count++;
                        }
                        currentIdx++;
                    }
                }

            } 
            else if (cmd[i].equals("Z")) {
                // 최근 삭제된 부분 꺼내서 O로 변경
                int restoration = deleted.pop();
                tableStatus[restoration] = "O";
            }
        }

        StringBuilder answer = new StringBuilder();
        // 배열 속 문자열 합치기
        for(int i = 0; i < tableStatus.length; i++) {
            answer.append(tableStatus[i]);
        }
        return answer.toString();
    }
}

 

💡 풀이

최종 코드

1. 인덱스 기준 앞, 뒤 인덱스를 담는 배열을 2개 만든다.(맨 앞, 맨 뒤를 위해 배열 앞뒤로 추가 공간을 둔다.
2. 명령문 처리
   1. 삭제
      1. 스택에 삭제할 인덱스를 담는다.
      2. 앞뒤 인덱스가 가리키는 이전, 이후 인덱스를 변경한다.
      3. 현재 인덱스를 뒤로 하나 옮긴다.(마지막이라면 앞으로 하나 이동)
   2. 복구
      1. 삭제 배열에서 최근에 저장된 인덱스를 꺼낸다.
      2. 삭제할 때 변경한 인덱스들을 원래대로 돌려놓는다.
   3. 이동
      1. 이동할 거리만큼 반복문을 돌며 앞이나 뒤로 이동함
3. 정답 문자열 만들기
   1. 배열을 만들고 'O'로 채우기
   2. 삭제 배열을 돌며 해당 인덱스만 'X'로 변경
   3. new String()으로 배열을 문자열로 만들기

 

첫 코드

1. 상태 변경을 추적할 배열을 만든다.
2. 명령문 처리
   1. 이동
      1. 값이 X이면 뛰어넘고 앞이나 뒤로 이동한다.
   2. 삭제
      1. 스택에 삭제된 인덱스를 push 한다.
      2. 상태 추적 배열의 해당 인덱스 값을 "X"로 변경한다.
      3. 2-1과 동일하게 이동한다.
   3. 복구
      1. 최근 삭제된 인덱스를 꺼낸다.
      2. 상태 추적 배열의 해당 인덱스 값을 "O"로 변경한다.
3. 정답 문자열 만들기
   1. StringBuilder와 반복문을 이용해 배열을 문자열로 합친다.

 

💭 회고

정말 너무 안 풀렸던 문제였다..😖

지금까지는 설계 방식이 안 떠오르는게 아니면 최대한 책을 참고하지 않았다.

그런 면에서 이 문제는 어떻게 짤지는 금방 떠올라서 책에 의존하지 않고 구현을 했는데 계속 런타임 에러 또는 시간 초과가 떴다.

 

그렇게 질문 목록을 뒤지다가 힌트를 얻을 수 있었다.

위 또는 아래로 움직이실때 표에서 제거가 된 것들은 "X"로 마킹해서 스킵해주신 부분을 보면 정확성은 문제가 없지만 런타임 효율상 결국 "X"로 마킹된 부분까지 프로그램이 계속 훓고 있기 때문에 느려지고 있는 것 같습니다.

내 첫 코드를 보면 이동할 때마다 while문을 돌며 배열값을 바꾸고 문자열로 합칠 때도 반복문을 사용한다.

배열을 계속 훑고 값을 변경하니 시간이 많이 들었던 것이다.

솔직히 이동이 필요한 모든 상황에서 while문을 쓰니 비효율적이라고 느끼긴 했는데 머릿속 설계대로 짜려면 어쩔 수 없었다..

 

그래서 결국 책을 참고했다.

책에서는 각 행의 위아래 인덱스를 저장하는 배열을 따로 만들고, 명령어가 실행될 때마다 실행되는 위치 위, 아래 행의 인덱스를 변경하는 방식으로 이를 처리했다. 연결 리스트랑 비슷한 방식 같다.

 

새로 알게된 것 || 다시 떠오른 것

1. 삼항연산자
2. Arrays.fill(arr, val) - 빈 배열 채우기
3. new String(arr) - 배열값을 붙여 문자열로 만들기

 

앞으로 문제를 풀 때는

• 값이 아닌 인덱스만을 이용할 수 있는지 생각해 볼 것
• 반복문이 너무 많이 나오면 다른 방법을 생각해 볼 것