Programmers - 표 편집(Java)

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

코딩테스트 연습 - 표 편집

 

풀이

삭제와 복원 기능의 시간을 최소화하는 Linked List를 이용하여 풀이

 

Node의 연결 관계만 변경하면 삭제된 Node가 있더라도 이동 명령을 수행하기 편함

 

---

Linked List 정의 및 초기화

입력값 n의 최대값 만큼 Node 배열을 생성

0 ~ n-1 의 Node의 prev/next를 이전/다음 Node와 이어줌

삭제된 순으로 저장되는(FILO) delete Stack를 생성

 

처음 위치는 Node 배열의 k번째 요소에서 시작됨

 

이후 입력값(String[] cmd)의 순서에 맞게 하나씩 명령 실행

static class Node {
	Node prev = null;
	Node next = null;
	boolean isDelete;
}

public static String solution(int n, int k, String[] cmd) {
	Node[] nodeArr = new Node[1000001];

	nodeArr[0]=new Node();
	for (int i = 1; i < n; i++) {
		nodeArr[i]=new Node();
		nodeArr[i].prev=nodeArr[i-1];
		nodeArr[i-1].next=nodeArr[i];
	}
	Stack<Node> delete= new Stack<>();
	Node now =nodeArr[k];
    
	for(String query : cmd){
		char command = query.charAt(0);
		.
		.
		.
	}
    .
    .
    .

 

 

위/아래로 이동의 경우

위/아래 이동의 경우 해당 X(cnt)에 맞게 prev/next로 이동

for(String query : cmd){
	char command = query.charAt(0);

	// 위로 이동
	if(command == 'U'){
		int cnt = Integer.parseInt(query.substring(2));
		for(int i=0;i<cnt;i++) now=now.prev;
	}
	
	// 아래로 이동
	else if(command == 'D') {
		int cnt = Integer.parseInt(query.substring(2));
		for(int i=0;i<cnt;i++) now=now.next;
	}
    .
    .
    .

 

 

현재 위치 삭제

현재 노드를 삭제처리하고 Stack에 삽입한다.

현재 기준 이전/이후 노드를 갱신

다음 Node가 있다면 현재 위치는 next, 다음 Node가 없다면 현재 위치는 prev의 Node가 된다.

 

else if(command =='C'){
	now.isDelete=true;
	delete.push(now);

	Node prev=now.prev;
	Node next=now.next;

	if(prev!=null){
		prev.next=next;
	}
	if(next!=null){
		next.prev=prev;
		now=next;
	}
	else{
    	now=prev;
	}
}

 

 

최근 삭제된 행 되돌리기

Stack에서 Pop한 노드(가장 최근에 삭제된 노드)에 대해 작업

해당 노드와 이전/이후 노드를 연결

else{
	Node node = delete.pop();
	Node prev=node.prev;
	Node next=node.next;

	node.isDelete=false;
	if(prev!=null){
		prev.next=node;
	}
	if(next!=null){
		next.prev=node;
	}
}

* 삭제된 순으로 복원되기 때문에 복원과정이 비교적 간단, 순서가 정해져 있지 않았다면 복잡한 구성으로 이뤄졌을 듯

---

전체 코드

import java.util.Stack;

class Solution {
    static class Node {
        Node prev = null;
        Node next = null;
        boolean isDelete;
    }

    public static String solution(int n, int k, String[] cmd) {
        Node[] nodeArr = new Node[1000001];

        nodeArr[0]=new Node();
        for (int i = 1; i < n; i++) {
            nodeArr[i]=new Node();
            nodeArr[i].prev=nodeArr[i-1];
            nodeArr[i-1].next=nodeArr[i];
        }

        Stack<Node> delete= new Stack<>();
        Node now =nodeArr[k];

        for(String query : cmd){
            char command = query.charAt(0);

            // 위로 이동
            if(command == 'U'){
                int cnt = Integer.parseInt(query.substring(2));
                for(int i=0;i<cnt;i++){
                    now=now.prev;
                }
            }
            // 아래로 이동
            else if(command == 'D') {
                int cnt = Integer.parseInt(query.substring(2));
                for(int i=0;i<cnt;i++){
                    now=now.next;
                }
            }
            // 현재 위치 삭제
            else if(command =='C'){
                now.isDelete=true;
                delete.push(now);

                Node prev=now.prev;
                Node next=now.next;

                if(prev!=null){
                    prev.next=next;
                }
                if(next!=null){
                    next.prev=prev;
                    now=next;
                }
                else{
                    now=prev;
                }
            }
            // 최근 삭제된 행 되돌리기
            else{
                Node node = delete.pop();
                Node prev=node.prev;
                Node next=node.next;

                node.isDelete=false;
                if(prev!=null){
                    prev.next=node;
                }
                if(next!=null){
                    next.prev=node;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++){
            if(nodeArr[i].isDelete) sb.append('X');
            else sb.append('O');
        }

        return sb.toString();
    }
}