[PGM]표 편집

티어 : Lv. 3
정답여부 : 오답

💡문제

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

 

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

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

예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).

 

다음으로 "U 3"을 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다.

 

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

다음으로 "U 2"를 수행하면 현재 선택된 행은 2행이 됩니다.

 

위 상태에서 "Z"를 수행할 경우 가장 최근에 제거된 "라이언"이 적힌 행이 원래대로 복구됩니다.

 

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

이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 "O", 삭제된 행은 "X"로 표시하면 다음과 같습니다.

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

 

제한사항

• 5 ≤ n ≤ 1,000,000
• 0 ≤ k < n
• 1 ≤ cmd의 원소 개수 ≤ 200,000
• 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
• 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없습니다.
• 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.

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

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

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

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

💡입출력 예

💡문제 분석 요약 

• 처음 표와 현재 표의 값이 같으면 ⭕️을 틀리면 ❌ 출력하면 되는 문제

💡알고리즘 설계

• n, table_size : 현재 표의 행의 개수
• k : 현재 위치
• cmd : 각 명령어
• stack : 삭제를 위한 명령어

1. 1. 각각 명령문은 반복하는데
   2. D : 해당 위치에 숫자만큼 k+ , U는 반대 k-

      Integer.parseInt(cmd[i].substring(2));
      // 해다 위치에 있는 값에 끝부분을 가져와 정수형으로 만듬
      

   3. —> string값으로 정수형으로 변환
   4. C : 해당 커서 위치를 삭제하고 삭제한 행을 stack에 저장—> 삭제한 행이 있는 경우 deleted에 그 위치에 True
   5. —> 마지막 커서가 마지막 행이면 커서를 1 감소
   6. Z : 최근에 삭제한 행을 stack에서 pop
   7. —> 삭제한 행을 다시 돌리면 deleted에 그 위치에 false
   8. 처음 표와 현재 표를 비교하여 같으면 같으면 ⭕️을 틀리면 ❌ 출력

💡시간복잡도

• O(N)

 

💡코드

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        StringBuilder answer = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        boolean[] deleted = new boolean[n]; // 삭제된 행을 표시하는 배열
        int table_size = n;

        for (String command : cmd) {
            char c = command.charAt(0);
            
            if (c == 'D') {
                k+= Integer.parseInt(command.substring(2));
            } else if (c == 'U') {
                k -= Integer.parseInt(command.substring(2));
            } else if (c == 'C') {
                stack.push(k);
                deleted[k] = true;
                table_size--;

                // 테이블의 마지막 행을 삭제했을 경우
                if (k == table_size - 1) {
                    k--;
                }
            } else if (c == 'Z') {
                int restoredIndex = stack.pop();
                deleted[restoredIndex] = false;
                table_size++;
            }
        }

        for (int i = 0; i < n; i++) {
            if (deleted[i]) {
                answer.append("X");
            } else {
                answer.append("O");
            }
        }

        return answer.toString();
    }
}

 

💡 틀린 이유

코드 실행시 결과는 나왔지만.. 시간복잡도나 효율성 ..등등 아예 틀렸다고 나온다..

그래서 다른 사람 코드를 보는와중 정말 간단하고 개쩌는 코드를 발견했다.

여기서 조금 놀란부분은 현재 표와 처음 표를 비교하는 부분에서 stack이 비어있지 않은 경우 삭제한 위치에 x를 넣는것을 보고 .. 다르다 생각을 했다.

 

💡 틀린 부분 수정 or 다른 풀이

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        // 삭제된 행의 인덱스를 저장하는 스택
        Stack<Integer> stack = new Stack<Integer>();
        
        // 현재 표의 크기를 저장하는 변수
        int table_size = n;
        
        // 명령어 처리 루프
        for(int i=0; i<cmd.length; i++) {
            char c = cmd[i].charAt(0);
            
            // "D x" 명령어 처리
            if(c=='D')
                k+=Integer.parseInt(cmd[i].substring(2));
            
            // "U x" 명령어 처리    
            else if(c=='U')
                k-=Integer.parseInt(cmd[i].substring(2));
            
            // "C" 명령어 처리
            else if(c=='C') {
                // 현재 커서 위치의 행을 삭제하고 스택에 저장
                stack.add(k);
                table_size--;
                
                // 만약 현재 커서가 마지막 행이었다면 커서를 1 감소시킴
                if(k==table_size)
                    k--;
            }
            
            // "Z" 명령어 처리
            else if(c=='Z') {
                // 가장 최근에 삭제된 행의 인덱스를 스택에서 pop
                if(stack.pop()<=k)
                    k++;
                table_size++;
            }
        }
        
        // 최종 결과 문자열 생성
        StringBuilder answer = new StringBuilder();
        for(int i=0; i<table_size; i++)
            answer.append("O");
        while(!stack.isEmpty())
            answer.insert(stack.pop().intValue(), "X"); //해당 인덱스에 x를 넣어줌
        return answer.toString();
    }
}

 

💡 느낀점 or 기억할정보

가져온 코드가 책에 있는코드보다 좀 더 쉽고 이해가 잘가는거 같다.. 그리고 굳이 나처럼 boolean이 없이도 stack만 이용하여 비교를 할 수 있구나.. 한 수 배워간다.