[PG] 표 편집 - Java

https://programmers.co.kr/learn/courses/30/lessons/81303?language=java 

코딩테스트 연습 - 표 편집

[풀이]

1. up,down에서 처음에 0에서 UP 1 시 7(마지막)으로 가는 것으로 이해했으나, 문제에서 친절히 표 범위를 벗어나는 입력은 주어지지 않는다고 했었다.

2. LinkedList처럼 노드를 연결해서 문제를 푼다.

3. 제거 C 할 때 맨 첫 행이면 prev갱신 안해도 되고, 마지막 행이면 next 갱신을 안해도 되는 것을 주의하자

4. 제거할 때 그 노드 자체를 stack에 넣어두면 다시 복원할 때 그 노드는 앞,뒤 정보를 가지고 있기 때문에 그대로 관계를 복원할 수 있다.

 

[시간초과 코드]

import java.util.*;

class Solution {
    static StringTokenizer st;
    static Stack<Integer> deleteQueue = new Stack<>();
    static ArrayList<Point> pointArr = new ArrayList<>();
    static int now = 0;
    
    public String solution(int n, int k, String[] cmd) {
        for(int i=0;i<n;i++){
            pointArr.add(new Point(i));
        }
        now = k;
        pointArr.get(k).isNow = true;
        
        for(int c = 0;c<cmd.length;c++){
            st = new StringTokenizer(cmd[c]);
            char command = st.nextToken().charAt(0);
            if(command=='U'){
                int diff = Integer.parseInt(st.nextToken()); //diff 칸만큼 이동해야함
                int newNum = now;
                while(diff>0){
                    newNum -= 1;
                    if(newNum<0){
                        newNum = n - newNum % n;
                    }
                    if(pointArr.get(newNum).isDelete){
                        continue;
                    }
                    else{
                        diff--;
                    }
                }
               
                pointArr.get(now).isNow = false;
                now = newNum;
                pointArr.get(now).isNow = true;
            }
            else if(command=='D'){
                int diff = Integer.parseInt(st.nextToken());
                int newNum = now;
                
                while(diff>0){
                    newNum += 1;
                    if(newNum>=n){
                        newNum = newNum%n;
                    }
                    if(pointArr.get(newNum).isDelete){
                        continue;
                    }
                    else{
                        diff--;
                    }
                }
                pointArr.get(now).isNow = false;
                now = newNum;
                pointArr.get(now).isNow = true;
                //System.out.println("DOWN NOW! "+now);
            }
            else if(command=='C'){
                pointArr.get(now).isDelete = true;
                deleteQueue.add(now);
                int diff = 1;
                int newNow = now;
                
                if(now==n-1){ //가장 마지막 행인 경우 바로 윗 행 선택
                    while(diff>0){
                        newNow -= 1;
                        if(pointArr.get(newNow).isDelete){
                            continue;
                        }
                        else{
                            diff--;
                        }
                    }
                    pointArr.get(now).isNow = false;
                    now = newNow;
                    pointArr.get(now).isNow = true;
                }
                else{
                    while(diff>0){
                        newNow += 1;
                        if(pointArr.get(newNow).isDelete){
                            continue;
                        }
                        else{
                            diff--;
                        }
                    }
                    pointArr.get(now).isNow = false;
                    now = newNow;
                    pointArr.get(now).isNow = true;
                }
            }
            else if(command=='Z'){
                int queue = deleteQueue.pop();
                pointArr.get(queue).isDelete = false;
                //System.out.println("/////DELETE - "+queue);
            }
            //System.out.println("===NOW : "+now);
            //System.out.println(pointArr);
        }
        String answer = "";
        for(Point point:pointArr){
            if(point.isDelete){
                answer+='X';
            }
            else{
                answer+='O';
            }
        }
        return answer;
    }
    
    static class Point{
        int idx;
        boolean isDelete;
        boolean isNow;
        public Point(int idx){
            this.idx = idx;
            this.isDelete = false;
            this.isNow = false;
        }
        public Point(int idx, boolean d, boolean n){
            this.idx = idx;
            this.isDelete = false;
            this.isNow = false;
        }
        @Override
        public String toString(){
            return "IDX="+idx+" DE:"+isDelete+" Now:"+isNow;
        }
    }
}

[통과 코드]

class Solution {
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static ArrayList<Node> NodeArr = new ArrayList<>();
    static Stack<Node> deleteStack = new Stack<>();

    static Node now;
    public static String solution(int n, int k, String[] cmd) {
        Node root = new Node(0);
        NodeArr.add(root);

        for(int i=1;i<n;i++){
            NodeArr.add(new Node(i));
            NodeArr.get(i).prev = NodeArr.get(i-1);
            NodeArr.get(i-1).next = NodeArr.get(i);
        }

        now = NodeArr.get(k);

        for(int c = 0;c<cmd.length;c++){
            st = new StringTokenizer(cmd[c]);
            char command = st.nextToken().charAt(0);
            if(command=='U'){
                int diff = Integer.parseInt(st.nextToken()); //diff 칸만큼 이동해야함

                for(int i=0;i<diff;i++){
                    now = now.prev;
                }
            }
            else if(command=='D') {
                int diff = Integer.parseInt(st.nextToken()); //diff 칸만큼 이동해야함
                for(int i=0;i<diff;i++){
                    if(now.next==null){
                        break;
                    }
                    now = now.next;
                }
            }
            else if(command=='C') {
                //제거
                now.isDelete = true;
                deleteStack.add(now);
                //앞뒤관계 수정하기
                Node before = now.prev;
                Node after = now.next;
                if(before!=null){ //now가 첫 행이면 before 갱신 안해도 됨
                    before.next = after;
                }
                if(after!=null){ //now가 마지막 행이면 next 갱신 안해도 됨
                    after.prev = before;
                }

                //마지막 행이면 now 윗 행 선택
                if(after==null){
                    now = before;
                }
                //나머지는 아래 행 선택
                else{
                    now = after;
                }
            }
            else if(command=='Z') {
                //이전에 제거했던 거에서 pop해서 다시 관계 살리기
                Node pop = deleteStack.pop();
                Node before = pop.prev;
                Node after =  pop.next;
                pop.isDelete = false;

                if(before!=null){
                    before.next = pop;
                }
                if(after!=null){
                    after.prev = pop;
                }
            }
        }

        for(Node node:NodeArr){
            if(node.isDelete){
                sb.append("X");
            }
            else{
                sb.append("O");
            }
        }
        return sb.toString();
    }
    
    static class Node{
        int idx;
        Node prev = null;
        Node next = null;
        boolean isDelete;

        public Node(int idx) {
            this.idx = idx;
        }
    }
}