[프로그래머스] 표 편집

문제

풀이

import java.util.*;
class Solution {
    
    private static final char UP = 'U';
    private static final char DOWN = 'D';
    private static final char CUT = 'C';
    private static final char RESTORE = 'Z';
        
    public String solution(int n, int k, String[] cmd) {
        Stack<Node> deletedNode = new Stack<Node>();
        Node root = new Node(0);
        Node currentNode = root;
        for (int i = 1; i < n; i++) {
            Node node = new Node(i);
            currentNode.setNext(node);
            node.setPrevious(currentNode);
            currentNode = node;
        }
        
        Node end = currentNode;
        currentNode = root;
        
        while (k-- > 0) {
            currentNode = currentNode.getNext();
        }

        int cmdLength = cmd.length;
        for (int i = 0; i < cmdLength; i++) {
            char c = cmd[i].charAt(0);
            if (c == UP) {
                int moveCount = Integer.parseInt(cmd[i].substring(2));
                for (int j = 0; j < moveCount; j++) {
                    currentNode = currentNode.getPrevious();
                }
            } else if (c == DOWN) {
                int moveCount = Integer.parseInt(cmd[i].substring(2));
                for (int j = 0; j < moveCount; j++) {
                    currentNode = currentNode.getNext();
                }
            } else if (c == CUT) {
                deletedNode.add(currentNode);
                
                if (currentNode == root) {
                    currentNode = currentNode.getNext();
                    currentNode.setPrevious(null);
                    root = currentNode;
                } else if (currentNode == end) {
                    currentNode = currentNode.getPrevious();
                    currentNode.setNext(null);
                    end = currentNode;
                } else {
                    currentNode.getPrevious().setNext(currentNode.getNext());
                    currentNode.getNext().setPrevious(currentNode.getPrevious());
                    
                    currentNode = currentNode.getNext();
                }
            } else { // restore
                Node deleted = deletedNode.pop();
               
                if (deleted.getPrevious() == null) {
                    root = deleted;
                    root.getNext().setPrevious(root);
                } else if (deleted.getNext() == null) {
                    end = deleted;
                    end.getPrevious().setNext(end);
                } else {
                    deleted.getNext().setPrevious(deleted);
                    deleted.getPrevious().setNext(deleted);
                }
            }
        }
        
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; i++) {
            if (root != null && root.getData() == i) {
                sb.append("O");
                root = root.getNext();
            } else {
                sb.append("X");
            }
        }
        return sb.toString();
    }
    class Node {
		private Node previous;
		private Node next;
		private int data;
        public Node(int data) {
            this.data = data;
            previous = null;
            next = null;
        }
		public Node getPrevious() {
			return previous;
		}
		public void setPrevious(Node previous) {
			this.previous = previous;
		}
		public Node getNext() {
			return next;
		}
		public void setNext(Node next) {
			this.next = next;
		}
		public int getData() {
			return data;
		}
		public void setData(int data) {
			this.data = data;
		}
		
		
	}
}

• 연결리스트를 이용한 문제풀이
• Node 객체를 만들어서 next, previous로 모든 노드들을 연결해 준다.
• 삭제 및 복원시 next, previous 노드가 바뀌면서 추가/삭제 된다.

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