[프로그래머스] 표 편집

문제 설명

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

문제 풀이

• 효율성 테스트가 까다로운 문제였다.
• 일반적으로 문자열에 대한 이해만 있다면 정확성 테스트는 쉽게 통과가 가능하다.
• 처음엔 결과 배열만 놓고 인덱스를 이동할때 'X'인 인덱스는 건너뛰는 방식으로 구현하였다 -> 시간초과
• 문제는 리스트에서 노드를 삭제하고 복원하는 문제인데 이 때 연결 리스트를 활용하면 아주 편하게 구현이 가능하다.
• 연결 리스트를 활용하는 이유는 복원에 아주 최적화가 되어 있기 때문이다
  
• 위 그림처럼 삭제된 노드를 저장공간(문제에서는 스택)에 보관해두면 복원시에 prev, next를 그대로 저장하고 있기 때문에 복원이 아주 편리하다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public class Node {
        int n;
        Node prev;
        Node next;

        public Node(int n, Node prev, Node next) {
            this.n = n;
            this.prev = prev;
            this.next = next;
        }
    }

    public String solution(int n, int k, String[] cmd) {
        //초기화
        char[] result = new char[n];
        Arrays.fill(result, 'O');

        Stack<Node> stack = new Stack<>();
        Node cur = new Node(-1, null, null);
        for (int i = 0; i < n; i++) {
            Node next = new Node(i, cur, null);
            cur.next = next;
            cur = next;
        }
        cur.next = new Node(-1, cur, null);

        //현재 cur은 n-1번째 노드
        for (int i = 0; i < n-k-1; i++)
            cur = cur.prev;

        //현재 cur은 k번째 노드
        //명령 실행
        StringTokenizer st;
        for (String c : cmd) {
            st = new StringTokenizer(c);
            String first = st.nextToken();
            if (first.equals("U")) {
                int num = Integer.parseInt(st.nextToken());
                while(num-- > 0)
                    cur = cur.prev;
            } else if (first.equals("D")) {
                int num = Integer.parseInt(st.nextToken());
                while(num-- > 0)
                    cur = cur.next;
            } else if (first.equals("C")) {
                Node prev = cur.prev;
                Node next = cur.next;
                result[cur.n] = 'X';
                stack.push(cur);
                prev.next = next;
                next.prev = prev;
                if (next.n != -1) cur = next;
                else cur = prev;
            } else if (first.equals("Z")) {
                Node recover = stack.pop();
                result[recover.n] = 'O';
                Node prev = recover.prev;
                Node next = recover.next;
                prev.next = recover;
                next.prev = recover;
            }
        }

        return String.valueOf(result);
    }
}