[2021 카카오 채용연계형 인턴십] 표 편집

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/81303

이 문제는 스택을 이용하여 풀 수 있습니다. 이 문제는 데이터가 삭제되었는지 아닌지만 체크해서 보여주면 됩니다. 따라서 삭제 시 스택에 삭제된 행 번호를 저장하고 복구 시 스택의 가장 위의 값을 제거하는 방식으로 삭제된 데이터를 관리할 수 있습니다. 이 때 삭제 및 복구 시 데이터 전체 길이도 그에 맞게 수정해주셔야 합니다. 또한 복구 시 현재 위치보다 위의 데이터가 복구될 경우 현재 위치값을 1만큼 증가시켜야 보정이 됩니다. 모든 명령을 수행한 후 현재 데이터 길이만큼 O를 추가한 후 스택에 저장된 행 번호 위치 다음에 X를 추가한다면 삭제된 데이터 행 번호를 확인할 수 있습니다.

여기서 삭제된 데이터를 무시하지 않고 이동했을 경우 선택된 행이 잘못 체크되는 것이 아닌가 하실 수 있습니다. 결론부터 말씀드리자면 행 번호는 상대적으로 결정되기 때문에 무시하고 진행하여도 문제가 없습니다. 최종 데이터를 가져오는 방식이 삭제된 데이터의 행 번호를 기존 데이터에 추가하는 방식입니다. 따라서 데이터의 행 번호는 절대적일 필요가 없으며 현재 데이터 구조에서의 순서값으로 계산하여도 문제가 없습니다. 이 때 삭제된 데이터의 행 번호는 가장 최근일수록 명령을 완료했을 때의 결과 데이터와 가장 유사합니다. 이 때 데이터를 스택에서 관리하기 때문에 자연스럽게 가장 먼저 추가되는 삭제된 데이터 행 번호는 가장 최근에 삭제된 데이터이므로 순서에 이상이 없습니다. 해당 데이터가 추가된 이후 다음 스택의 가장 위의 데이터는 마찬가지로 삭제 당시의 데이터 구조와 같기 때문에 역시 순서에 이상이 없습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static int curr,size;
    static Stack<Integer> deleted = new Stack<>();
    
    static void moveDown(int cnt){
        curr += cnt;
    }
    
    static void moveUp(int cnt){
        curr -= cnt;
    }
    
    static void delete(){
        deleted.push(curr);
        size--;
        
        // 삭제된 행이 가장 마지막 행인 경우 바로 윗 행 선택
        if(curr == size) curr--;
    }
    
    static void restore(){
        int val = deleted.pop();
        size++;
        
        // 복구된 행이 현재 위치보다 위에 있을 경우 현재 위치 1 증가
        if(val <= curr) curr++;
    }
    
    public String solution(int n, int k, String[] cmd) {
        curr = k;
        size = n;
        
        for(int i=0;i<cmd.length;i++){
            StringTokenizer st = new StringTokenizer(cmd[i]);
            String command = st.nextToken();
            if(command.equals("C")) delete();
            else if(command.equals("Z")) restore();
            else{
                int cnt = Integer.parseInt(st.nextToken());
                if(command.equals("D")) moveDown(cnt);
                else if(command.equals("U")) moveUp(cnt);
            }
        }
        
        StringBuilder answer = new StringBuilder();
        for(int i=0;i<size;i++){
            answer.append("O");
        }
        
        while(!deleted.isEmpty()){
            int idx = deleted.pop();
            answer.insert(idx,"X");
        }
        
        return answer.toString();
    }
}