프로그래머스 - 표 편집

leehyunjon·2022년 4월 28일

Algorithm

목록 보기

13/162

표 편집 : https://programmers.co.kr/learn/courses/30/lessons/81303#

Problems

Solves

첫번째 풀이에서는 튜플들을 저장하는 LinkedList, 삭제 튜플을 저장하는 Stack으로 구현을 했었다.
테스트케이스를 돌려보니 튜플 삭제와 복구에서 튜플의 위치가 꼬이고 런타임이 발생해서 다른 분의 풀이를 참고하였다.

LinkedList와 Stack으로 접근하는 방법은 맞았지만 LinkedList를 응용해서 사용하는 방법이었다.
튜플을 LinkedList에 직접 저장하는 것이 아닌 튜플의 이전 튜플과 이후 튜플을 저장하는 배열 int[] prev와 int[] next를 통해서 구현하였다.
풀이는 아래와 같다.

각 index를 튜플의 고유값이라 가정하고 각 튜플의 이전 튜플은 prev배열에, 이후 튜플은 next배열에 초기화한다.
StringBuilder를 통해 각 튜플의 상태를 나타낸다('O')
cmd를 돌면서 명령어(method)를 가져와서 현재 가리키고 있는 튜플(cursor) 이동과 삭제, 복구 작업 그리고 튜플의 상태를 갱신한다.
튜플 상태값 반환

문제에 주어진 테스트케이스를 그림으로 보면 아래와 같다.

처음 추어진 배열들의 상태와 시작 점이 주어진 상황
cmd : 'D 2' 그리고 'C'가 발생한 상황

'D 2'로 인해 cursor가 2에서 4로 이동 했고 4행의 튜플이 삭제되어 이전 튜플(3행)과 이후 튜플(5행)이 서로 연결된다.
그리고 cursor는 삭제된 행이 마지막 행이 아니므로 다음 튜플(5행)이 4행의 위치가 된다.
삭제 stack에는 (4행 튜플이 저장된다)
현재 튜플들의 상태 : OOOOXOOO
cmd : 'U 3' 그리고 'C'가 발생한 상황

현재 튜플들의 상태 : OXOOXOOO
cmd : 'D 4' 그리고 'C'가 발생한 상황

삭제된 5행 튜플은 표의 가장 마지막 튜플이었기 때문에 cursor는 삭제된 튜플의 이전 튜플을 가리키게 된다.
현재 튜플들의 상태 : OXOOXOOX
cmd : 'U 2' 그리고 'Z'가 발생한 상황

복구를 시킬 때는 복구시킨 튜플의 이전 튜플이었던 튜플(6)의 next를 복구시킨 튜플(7)로 갱신, 이후 튜플이었던 튜플(-1)은 없는 튜플이니 무시한다.
현재 튜플들의 상태 : OXOOXOOO
cmd : 'Z'가 발생한 상황

복구를 시킬 때는 복구시킨 튜플의 이전 튜플이었던 튜플(0)의 next를 복구시킨 튜플(1)로 갱신, 이후 튜플이었던 튜플(2)의 prev를 복구시킨 튜플(1)로 갱신한다.
현재 튜플들의 상태 : OOOOXOOO

위의 순서를 마치게 되면 결과적으로 아래와 같다.

기존 4행 튜플만 삭제되고 나머지 튜플은 유지되고 있으므로 각 튜플의 상태는 OOOOXOOO가 된다.

Code

import java.util.Stack;
class Solution {
    Stack<Tuple> deletes;
    public String solution(int n, int k, String[] cmd) {
    	//각 튜플의 이전값
        int[] prev = new int[n];
        //각 튜플의 이후값
        int[] next = new int[n];
        //삭제된 튜플 저장
        deletes = new Stack<>();
        
        StringBuilder status = new StringBuilder();
        //각 튜플의 상태와 이전,이후 튜플 초기화
        for(int i=0;i<n;i++){
            status.append('O');
            prev[i]=i-1;
            next[i]=i+1;
        }
        //표의 마지막 행의 튜플의 next는 없으므로 -1로 갱신
        next[next.length-1]=-1;
        
        //시작 튜플 위치
        int cursor = k;
        for(String command : cmd){
            String[] c = command.split(" ");
            String method = c[0];
            int move = 0;
            switch(method){
                case "D":
                    move = Integer.parseInt(c[1]);
                    while(move-- > 0) cursor = next[cursor];
                    break;
                case "U":
                    move = Integer.parseInt(c[1]);
                    while(move-- > 0) cursor = prev[cursor];
                    break;
                case "C":
                	//삭제되는 튜플의 이전, 이후 튜플을 함께 저장
                    deletes.add(new Tuple(prev[cursor], cursor, next[cursor]));
                    //맨 처음에 있는 튜플이 아니라면 삭제하려는 튜플의 이전튜플의 다음 튜플은 삭제하려는 튜플의 다음 튜플을 가리킨다.
                    //(삭제하는 튜플이 가장 마지막에 있다면 삭제하려는 튜플의 이전 튜플의 다음 튜플은 없는 -1을 가리킨다.)
                    if(prev[cursor]!=-1) next[prev[cursor]] = next[cursor];
                    //마지막에 있는 튜플이 아니라면 삭제하려는 튜플의 다음튜플의 이전 튜플은 삭제하려는 튜플의 이전 튜플을 가리킨다.
                    //(삭제하는 튜플이 가장 처음에 있는 튜플이라면 삭제하려는 튜플의 다음 튜플의 이전 튜플은 없는 -을 가리킨다.)
                    if(next[cursor]!=-1) prev[next[cursor]] = prev[cursor];
                    
                    //삭제하려는 튜플의 상태값을 변경.
                    status.setCharAt(cursor, 'X');
                    
                    //cursor의 이동
                    if(next[cursor]!=-1) cursor = next[cursor];
                    else cursor = prev[cursor];
                    break;
                case "Z":
                    Tuple t = deletes.pop();
                    //복구된 튜플의 이전 튜플은 복구된 튜플을 다시 가리킨다.
                    if(t.prev != -1) next[t.prev] = t.num;
                    //복구된 튜플의 이후 튜플은 복구된 튜플을 다시 가리킨다.
                    if(t.next != -1) prev[t.next] = t.num;
                    
                    //복구된 튜플의 상태값 변경.
                    status.setCharAt(t.num,'O');
                    break;
            }
        }
        
        return status.toString();
    }
    
    class Tuple{
        int prev;
        int num;
        int next;
        public Tuple(int prev, int num, int next){
            this.prev = prev;
            this.num = num;
            this.next = next;
        }
    }
}