프로그래머스_표 편집(JAVA)

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

코딩테스트 연습 - 표 편집

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(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
  • 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

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

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

---

입출력 예

n	k	cmd	result
8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]	"OOOOXOOO"
8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]	"OOXOXOOO"

---

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

다음은 9번째 명령어까지 수행한 후의 표 상태이며, 이는 입출력 예 #1과 같습니다.

10번째 명령어 "U 1"을 수행하면 "어피치"가 적힌 2행이 선택되며, 마지막 명령어 "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "제이지"가 적힌 행을 선택합니다.

따라서 처음 주어진 표의 상태와 최종 표의 상태를 비교하면 다음과 같습니다.

---

[문제 분석]

정확성 테스트를 통과하는 코드를 짜기는 쉬웠지만 계속해서 효율성 테스트에서 시간초과가 났다.

효율성 테스트에서 시간초과가 난 코드의 풀이는 다음과 같다.

ArrayList al에 0부터 n-1까지 저장하고 String answer는 "X" n개로 초기화한다.

int cur는 현재 선택된 행 번호이다. 만약 0 - 무지, 1 - 콘, 2 - 어피치, 3 - 제이지, 4 - 프로도로 구성된 테이블이 있다고 가정해보자. 현재 행번호 2번 어피치가 선택되어있고 이 행이 삭제됐다면, 변경된 cur의 값은 3이다. 테이블에 저장된 인덱스 값을 저장하려면 2를 저장해야겠지만 나중에 복구할 때를 대비해서 값으로 저장해두었다. 즉, 다르게 얘기하자면 이름인 제이지를 저장한 것이나 마찬가지다. 그리고 삭제한 2번 어피치는 stack del에 저장한다. 그리고 ArrayList al에서 해당 행을 삭제한다. 복구는 가장 나중에 삭제한 행을 복구하는 것이므로, LIFO가 지켜져야 한다. 따라서 Stack에 해당 행을 저장해주었다.

그리고 복구할 때에는 Arraylist al에 순서대로 넣어주고, 해당 행은 모두 오름차순으로 이루어져있으므로 Collections.sort(al)을 이용해서 정렬해주었다. 이를 통해 해당 행이 어디에 들어가야할 지 인덱스를 따로 저장하지 않아도 해당 위치에 맞게 들어갈 수 있게 된다.

위 과정을 모두 마치면, al에 존재하는 값인 경우는 answer에서 해당 위치의 문자를 "O"로 변경한다.

다음과 같이 풀게되면 정확성 테스트는 모두 통과하지만 효율성 테스트를 통과하지 못한다.

그 이유를 보니 ArrayList의 사용 때문인 것 같다. 삭제와 삽입 위치를 찾을 때 0부터 시작되므로 이 부분에서 시간 초과가 나는 것 같다.

 

따라서 arraylist를 사용하지 않고 푸는 방법은 다음과 같다.

k는 입력으로 주어지는 현재 선택된 행인데, 뒤이어 선택되는 행들을 가리키는 변수를 따로 설정하지 않고 이 변수에 직접 대입해가며 사용할 것이다.

우선 입력으로 주어지는 명령어는 4가지로, "U", "D", "C", "Z" 이다. 

명령어 뒤에 숫자가 주어지는 경우는 "U"와 "D"로 명령어 다음 공백으로 구분되어있는 숫자는 두 명령어인 경우에만 검사하면 된다.

 

1. "U X" 

현재 선택된 행에서 X칸 위에 있는 행을 선택하는 것이므로, 현재 선택된 행을 가리키는 k값을 변경해주어야 한다.

cmd에 주어진 X는 문자열일 것이므로 Integer로 변경해주는 작업을 거쳐 k값에서 빼준다.

cmd[i]의 0번째 문자는 "U"일 것이고, 1번째 문자는 " " 공백이므로 2번째 문자부터 마지막 문자까지를 정수형으로 형변환해주면 된다.

k-=Integer.parseInt(cmd[i].substring(2));

 

2. "D X"

현재 선택된 행에서 X칸 아래에 있는 행을 선택하는 것이므로, 현재 선택된 행을 가리키는 k값을 변경해주어야 한다.

cmd에 주어진 X는 문자열일 것이므로 Integer로 변경해주는 작업을 거쳐 k값에 더해준다.

cmd[i]의 0번째 문자는 "D"일 것이고, 1번째 문자는 " " 공백이므로 2번째 문자부터 마지막 문자까지를 정수형으로 형변환해주면 된다.

k+=Integer.parseInt(cmd[i].substring(2));

 

3. "C"

현재 선택된 행을 삭제하는 명령어이다.

삭제할 행을 Stack del에 넣어준다. int table은 현재 테이블의 크기이다. 따라서 하나의 행을 삭제했으므로 table크기를 1 감소시킨다. 그리고 현재 선택된 행인 k값을 변경해주어야 하는데, table의 크기가 k와 같았다면 table의 마지막 행을 삭제한 것이다. 만약 k값을 그대로 둔다면 table 크기를 초과하는 k값이 될 것이므로, 현재 table의 마지막 행을 가리키도록 k값을 1 감소시켜야 한다. table의 크기보다 k값이 작았다면, 행이 삭제되면서 자동으로 한칸씩 앞으로 땡겨지는 구조이므로 변경없이 그대로 둔다.

 

4. "Z"

가장 최근에 삭제된 행을 복구하는 명령어이다.

Stack del에 넣어두었던 원소를 pop하고, 행을 복구했으므로 table의 크기를 다시 1 증가시켜준다.

해당 명령어는 현재 선택한 행을 변경시키지 않으므로 k값의 변경은 없다.

 

cmd의 모든 명령어에 대해 위의 과정이 완료되었다면, 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열을 생성해야한다. 

우선 table의 크기만큼 "O"를 이어붙인다.

그 다음 Stack del에 존재하는 행은 "X"로 표시해야하므로, stack del의 모든 원소에 대해, 원소를 pop하며 그 값에 해당하는 위치에 "X"를 삽입한다. 

 

---

[효율성 테스트 시간초과 코드]

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        ArrayList<Integer> al =new ArrayList<>();
        Stack<Integer> del =new Stack<>();
        int cur = k;    //현재 선택된 행
        for(int i=0;i<n;i++){
            answer+="X";
            al.add(i);
        }
        
        for(int i=0;i<cmd.length;i++){
         
            if(cmd[i].charAt(0)=='U'){
                cur = al.get(al.indexOf(cur)-Integer.parseInt(cmd[i].substring(2)));
                
            }
            else if(cmd[i].charAt(0)=='D'){
                if(al.indexOf(cur)+Integer.parseInt(cmd[i].substring(2))>=al.size())
                    cur = al.get(al.size()-1);
                else
                    cur = al.get(al.indexOf(cur)+Integer.parseInt(cmd[i].substring(2)));
            }
            else if(cmd[i].charAt(0)=='C'){
               
                del.push(cur);
                if(al.indexOf(cur)<al.size()-1)
                    cur=al.get(al.indexOf(cur)+1);
                else
                    cur=al.get(al.size()-2);
                al.remove(al.indexOf(del.peek()));
                
            }
            else{
                //Z
                al.add(del.pop());
                Collections.sort(al);
            }
        }
        
        for(int i=0;i<al.size();i++){
            answer = answer.substring(0,al.get(i))+"O"+answer.substring(al.get(i)+1);
        }
        return answer;
    }
}

---

[최종 코드]

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        int table = n;
        Stack<Integer> del =new Stack<>();
      
        for(int i=0;i<cmd.length;i++){
         
            if(cmd[i].charAt(0)=='U'){
                k-=Integer.parseInt(cmd[i].substring(2));
                
            }
            else if(cmd[i].charAt(0)=='D'){
                k+=Integer.parseInt(cmd[i].substring(2));
            }
            
            else if(cmd[i].charAt(0)=='C'){
                del.add(k);
                table--;
                if(k==table)
                    k--;
                
            }
            else{
                //Z
                if(del.pop()<=k)
                    k++;
                table++;

            }
        }
        
       StringBuilder builder = new StringBuilder();
        for(int i=0; i<table; i++)
            builder.append("O");
        while(!del.isEmpty())
            builder.insert(del.pop().intValue(), "X");
        String answer=builder.toString();
        
        return answer;
    }
}