[프로그래머스]표 편집

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

코딩테스트 연습 - 표 편집

 

문제

---

• "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

 

풀이

---

처음 풀 때는 링크드리스트와 스택을 이용할려고 했으나 계속 시간초과가 나서 고민하다가 다른분의 풀이를 참고 하면서 풀다보니 굳이 링크드리스트를 사용하지 않고 Z의 기능만 스택으로 구현해주고 푸는 방법으로 풀어보게되었다.

 

import java.util.Stack;
 
 public class EditTable {
     public String solution(int n, int k, String[] cmd) {
         
         //삭제 된 값을 순서대로 저장할 스택
         Stack<Integer> remove_val = new Stack<>();
         int table_size = n;
 
         for(int i = 0; i < cmd.length; i++){
             char c = cmd[i].charAt(0);
 
             //D면 정수형으로 변환해서 +
             if (c == 'D'){
                 k+= Integer.parseInt(cmd[i].substring(2));
             }
 
             //U면 정수형으로 변환해서 -
             else if (c == 'U'){
                 k-=Integer.parseInt(cmd[i].substring(2));
             }
 
             //C면 정수형으로 변환해서 삭제스택에다가 현재 포커스값을 넣는다.그다음 테이블 사이즈 줄여줌
             else if (c == 'C'){
                 remove_val.add(k);
                 table_size --;
 
                 //만약 k값이 마지막위치에 있다면 k값을 빼준다.
                 if (k == table_size){
                     k--;
                 }
 
                 //Z이면 스택에서 값을 빼낸다 만약 K값이 스택에서 나온값과 같다면 k++
             }else if (c == 'Z'){
                 if (remove_val.pop()<=k){
                     k++;
                 }
 
                 //표 사이즈 늘려줌
                 table_size++;
             }
         }
         StringBuilder sb = new StringBuilder();
 
         //현재 표 크기만큼 0을 채워넣는다.
         for(int i = 0; i<table_size; i++){
                 sb.append("O");
         }
 
         //스택에 k값을 넣었기때문에 insert로 k를 빼내서 k번째 자리에 X를 채워준다.
         while (!remove_val.isEmpty()){
             sb.insert(remove_val.pop(),"X");
         }
 
         String answer = sb.toString();
 
         return answer;
     }
 }