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

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

코딩테스트 연습 - 표 편집

저는 해당 문제를 LinkedList 개념을 이용해 문제를 해결하였습니다.

next, prev배열을 통해 이전 또는 이후의 값이 무엇인지 확인하고 isValid를 통해 해당 값이 유효한지를 확인하였습니다.

요소(현재)를 지울 때는 이전의 다음 값을 현재의 다음 값으로 다음의 이전 값을 현재의 이전 값으로 변경하여 이동할 때 현재 요소가 검색되지 않도록 하였습니다. 

 

import java.util.*;
class Solution {
    private static int move(int num,int now,int[] arr){
        for(int i = 0 ; i < num ; i++){
            // if(arr[now] = -1){
            //     return now;
            // }
            now = arr[now];
        }
        return now;
    }
    private static int doCmd(int now,
                             boolean[] isValid,
                             int[] prev,
                             int[]next,
                             String cmd,
                             ArrayDeque<Integer>stack){
        if("C".equals(cmd)){
            stack.push(now);
            isValid[now] = false;
            int prevIndex = move(1,now,prev);
            int nextIndex = move(1,now,next);
            if(prevIndex != -1){
                next[prevIndex] = nextIndex;
            }
            if(nextIndex != -1){
                prev[nextIndex] = prevIndex;
            }
            if(nextIndex != -1){
                now = nextIndex;
            }else{
                now = prevIndex;
            }
            return now;
        }
        if("Z".equals(cmd)){
            int index = stack.poll();
            isValid[index] = true;
            int prevIndex = move(1,index,prev);
            int nextIndex = move(1,index,next);
            if(prevIndex != -1){
                next[prevIndex] = index;
            }
            if(nextIndex != -1){
                prev[nextIndex] = index;
            }
            return now;
        }
        String[] temp = cmd.split(" ");
        int num = Integer.parseInt(temp[1]);
        if("D".equals(temp[0])){
            now = move(num,now,next);
            return now;
        }
        if("U".equals(temp[0])){
            now = move(num,now,prev);
            return now;
        }
        System.out.println("???");
        return -1;
    }
    public String solution(int n, int k, String[] cmds) {
        String answer = "";
        int[] prev = new int[n];
        int[] next = new int[n];
        boolean[] isValid = new boolean[n];
        Arrays.fill(isValid,true);
        for(int i = 0 ; i < n ; i++){
            prev[i] = i-1;
            next[i] = i+1;
        }
        next[n-1] = -1;
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int now = k;
        for(String cmd : cmds){
            now = doCmd(now,isValid,prev,next,cmd,stack);
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < n ; i++){
            if(isValid[i]){
                sb.append("O");
            }else{
                sb.append("X");
            }
        }
        answer = sb.toString();
        return answer;
    }
}