[JAVA] # 표 편집

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

표에서 진하게 칠한 칸은 선택한 행입니다. 한 번에 한 행만 선택할 수 있으며 표의 범위를 벗어날 수 없습니다. 이때 다음과 같은 명령어를 이용해 표를 편집합니다.

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

예를 들어 위 표에서 “D 2”를 수행하면 다음 그림의 왼쪽처럼 4행이 선택되며 “C”를 수행하면 선택된 행을 삭제하고 바로 아래 행이었던 “네오”가 적힌 행을 선택합니다.

다시 “U 3”을 수행한 다음 “C”를 수행한 후의 표 상태는 다음 그림과 같습니다.

다음으로 “D 4”를 수행한 다음 “C”를 수행한 후의 표 상태는 다음 그림과 같습니다. 5행이 표의 마지막 행이므로, 이 경우 바로 윗 행을 선택하는 점에 주의합니다.

“U 2”를 수행하면 현재 선택한 행은 2행이 됩니다.

위 상태에서 “Z”를 수행하면 가장 최근에 제거한 “라이언”이 적힌 행이 복구됩니다.

다시 한번 “Z”를 수행하면 그다음으로 제거한 “콘”이 적힌 행이 복구됩니다. 현재 선택된 행은 바뀌지 않는 점에 주의하세요.

최종 표의 상태와 처음 표의 상태를 비교해 삭제되지 않은 행은 “O”, 삭제된 행은 “X”로 표시하면 다음과 같습니다.

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택한 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 주어질 때, 모든 명령어를 수행한 후의 표의 상태와 처음 표의 상태를 비교해 삭제되지 않은 행은 O, 삭제된 행은 X로 표시해 문자열 형태로 반환하는 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를 순서대로 이어붙인 문자열 형태로 반환해주세요.

정확성 테스트 케이스 제약 조건

• 정확성 테스트 : 10초
• 5 ≤ n ≤ 1,000
• 1 ≤ cmd의 원소 개수 ≤ 1,000

효율성 테스트 케이스 제약 조건

• 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
• 주어진 조건 외 추가 제약 조건 없습니다.

입출력의 예

풀이

틀린 풀이

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        String[] answer = new String[n];
        Arrays.fill(answer, "O");
        Stack<Integer> del = new Stack<>();
        for(String c : cmd){
            // C 삭제 후 아래 행 선택
            if(c.equals("C")){
                answer[k]="X";
                del.push(k);
                boolean down = true;
                // 마지막 행인 경우
                if(k==n-1){
                    down = false;
                }
                // 밑이 삭제 된건지 확인
                while(true){
                    if(down){
                        if(answer[++k].equals("O")){
                            break;
                        }
                    }else {
                        if(answer[--k].equals("O")){
                            break;
                        }
                    }
                }
                continue;
            }
            // Z
            if(c.equals("Z")){
                answer[del.pop()]="O";
                continue;
            }
            
            // U X
            // D X
            String dire = c.substring(0,1);
            int num = Integer.parseInt(c.substring(2));
            boolean up = dire.equals("U");
            while(num>0){
                if(up){
                    if(answer[--k].equals("O")){
                        num--;
                    } 
                } else {
                    if(answer[++k].equals("O")){
                        num--;
                    } 
                }
            }
        }
        return String.join("",Arrays.asList(answer));
    }
}

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Integer> del = new Stack<>();
        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;
        }
        
        // 현재위치 인덱스
        k++;
        
        for(String c : cmd){
            if(c.equals("C")){ // k가 1인경우
                del.push(k); 
                // -1 0 1 2 3 4
                up[down[k]]=up[k]; // -1 0 0 2 3 4
                // 1 2 3 4 5 6
                down[up[k]]=down[k]; // 2 2 3 4 5 6 
                
                if(n<down[k]){
                    k=up[k];
                } else{
                    k=down[k]; // 2
                }
            } else if(c.equals("Z")){
                int reset = del.pop();
                down[up[reset]] = reset;
                up[down[reset]] = reset;
            } else{
                // U X
                // D X
                String[] sp = c.split(" ");
                int x = Integer.parseInt(sp[1]);
                for(int i=0; i<x; i++){
                    if(sp[0].equals("U")){
                        k=up[k];
                    } else{
                        k=down[k];
                    }    
                }  
            }
        }
        
        String[] arr = new String[n];
        Arrays.fill(arr, "O");
        for(int i : del){
            arr[i-1] = "X";
        }
        return String.join("",Arrays.asList(arr));
    }
}