[pro] 프로그래머스 level3 81303 표 편집 - 스택

[문제]

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

프로그래머스

 

[풀이]

LinkedList 등을 이용하여 실제 행을 삭제하고 복구하는 행동 없이(이 경우 삭제, 복구를 위한 탐색 시간 소요 때문에 효율성 테스트를 통과 못함) Stack을 이용해서 현재 행의 삭제 여부만 판단할 수 있도록 한다.

행 삭제 후 현재 행의 위치를 계속 바꿔주기 때문에 Stack에는 같은 행이 여러번 들어갈 수 있다. 따라서 남은 table size 만큼 "O"로 채워준 후, StringBuilder의 insert를 통해서 지워진 행에 맞춰서 "X"를 끼워넣을 수 있도록 한다. 

 

[코드]

 

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        
        //삭제 정보 스택에 관리
        Stack<Integer> s = new Stack();
        
        int size = n;
        
        for(int i=0; i<cmd.length; i++){
            char c = cmd[i].charAt(0);
            
            if(c=='U'){ //X칸 위에 있는 행 선택
                k -= Integer.parseInt(cmd[i].substring(2));
            }
            else if(c=='D'){ //X칸 아래 있는 행 선택
                k += Integer.parseInt(cmd[i].substring(2));
            }
            else if(c=='C'){ //현재 선택 행 삭제
                s.add(k);
                size--;
                if(k==size){ //마지막 행을 가리키고 있었다면
                    k--;
                }
            }
            else if(c=='Z'){ //이전 삭제 행 복구
                if(s.pop()<=k){
                    k++;
                }
                size++;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<size; i++){
            sb.append("O");
        }
        
        while(!s.isEmpty()){
            sb.insert(s.pop(), "X");
        }
        
        answer = sb.toString();
        
        return answer;
        
    }
}