[프로그래머스 / JAVA] 표 편집

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

문제

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).

 

풀이

처음 문제를 풀 때 생각한것은 stack에 제거된 index를 순차적으로 집어넣으면 나중에 꺼내면서 추가하는게 좋지 않을까 생각했다.

• "C" 와 "Z" 가 입력될 때마다 n 의 크기를 조정 한다.
• stack에 삭제된 행의 index를 저장한다. 
• 최종 n만큼 StringBuilder에 "O"를 repeat하고 
• 마지막으로 stack에서  해당 index를 꺼내면서 "X" 를 주입(insert)한다.

이렇게 했는데, (정답이 나왔지만) 다른 분들의 풀이를 보다가 내가 잘못 푼 것을 발견하였다. (출처: 빈둥벤둥 IT logging)

 

다시 푼 풀이

1. 각 행의 이전 행과 다음 행에 대한 정보를 담은 배열을 만든다.
2. 스택을 사용해 삭제한 행의 정보를 저장한다.
3. StringBuilder를 사용해 결과 문자열을 만든다.
4. 명령어를 하나씩 처리한다.

• U X : X칸 위로 이동
• D X : X칸 아래로 이동
• C : 현재 선택된 행을 삭제하고, 바로 아래 행을 선택.
        만약, 삭제된 행이 마지막 행이라면 바로 위 행을 선택한다.
• Z : 가장 최근에 삭제된 행을 복구한다. 복구된 행은 원래 있던 위치에 돌아간다.

5. 모든 명령어를 처리한 후, 결과 문자열을 반환한다.

정답

import java.util.Stack;

class Solution {
    public class Node {
        int pre;
        int cur;
        int nxt;

        public Node(int pre, int cur, int nxt){
            this.pre = pre;
            this.cur = cur;
            this.nxt = nxt;
        }
    }

    public String solution(int n, int k, String[] cmd) {
        int[] pres = new int[n];
        int[] nxts = new int[n];
        Stack<Node> stack = new Stack<>();
        StringBuilder sb = new StringBuilder("O".repeat(n));

        for(int i = 0 ; i < n; i++){
            pres[i] = i - 1;
            nxts[i] = i + 1;
        }
        nxts[n-1] = -1;

        for(String s : cmd){
            char c = s.charAt(0);
            if(c == 'U'){
                int num = Integer.parseInt(s.substring(2));
                while(num-- > 0) k = pres[k];
            } else if (c == 'D'){
                int num = Integer.parseInt(s.substring(2));
                while(num-- > 0) k = nxts[k];
            } else if (c == 'C'){
                stack.push(new Node(pres[k], k, nxts[k]));
                if(pres[k] != -1) nxts[pres[k]] = nxts[k];
                if(nxts[k] != -1) pres[nxts[k]] = pres[k];
                sb.setCharAt(k, 'X');

                if(nxts[k] != -1) k = nxts[k];
                else k = pres[k];
            } else {
                Node node = stack.pop();
                if(node.pre != -1) nxts[node.pre] = node.cur;;
                if(node.nxt != -1) pres[node.nxt] = node.cur;;
                sb.setCharAt(node.cur, 'O');
            }
        }

        return sb.toString();
    }
}

 

* insert는 앞에서부터 해당 index까지 다 찾아가는 것이라, n * n의 문제가 생긴다. 이를 까먹지 말자..

 

참조

https://moonsbeen.tistory.com/294#rp