[프로그래머스] 2021카카오 인턴십 : 표 편집 (java)

문제 보러 가기

이 문제는 정확도와 효율성 2가지를 만족해야 하는 문제였다.

행 개수 n <= 1,000,000이고 명령어 개수 200,000이므로 각 명령어당 전체 행 개수를 탐색하게 된다면 효율성을 만족하지 못한다. 즉, 단순히 배열에 담고 각 명령어로 인덱스 움직여 탐색하며 수행은 효율성에서 탈락

 

 

 

두 가지로 풀이가 가능하다

1. Linked List

2. Segment Tree

 

이 중에서 1번 Linked List로 풀이하였다.

 

링크드 리스트의 경우 삭제, 삽입은 O(1) 시간을 갖고, 탐색은 명령어로 "D X"가 주어질 경우 현재 노드에서 X만큼 움직이므로 O(X) 시간을 갖는다. 모든 X의 값이 1,000,000 이하인 경우만 주어지므로 효율성에서 성공할 수 있다.

 

삭제된 노드는 Stack <Node>에 담아 최신 것부터 가져와서 업데이트시켜주면 된다. 삽입시에도 역시 이전 이후 노드 관계만 연결시켜주면 되므로 O(1) 시간을 갖게 되어 효율성에서 성공할 수 있다.

 

 

 

 

 

 

풀이과정

 

각 Node는 이전 노드의 정보를 담는 prev와 다음 노드의 정보를 담는 next 노드의 값을 담는 data로 구성된다.

 

-이동(D X, U X)

D의 경우 next노드를 X만큼 이동해 curNode업데이트

U의 경우 prev노드를 X만큼 찾아 curNode업데이트

 

 

-삭제(C)

선택되어 있는 curNode의 prev노드의 next를 curNode의 next노드와 연결,

curNode의 next노드의 prev노드를 curNode의 prev노드와 연결하면 curNode만 빠져나오게 된다. 이렇게 삭제된 노드는 Stack에 넣어 되돌리기 명령어 수행 시에 사용한다.

* root, tail 노드가 삭제될 경우는 root, tail노드를 업데이트시켜줘야 함

 

예시)

2번이 선택되어있을 때 

"C"수행된 후

1번 노드의 다음 노드는 3번 노드가 되고 삭제된 후에 선택된 노드는 3번 노드가 된다.

2번 노드의 경우 노드끼리 연결된 리스트에서는 빠지지만, stack에서 되돌리기 수행 시에 바로 연결할 수 있도록 prev, next 노드 정보를 유지한다.

 

 

-되돌리기(Z)

stack에서 최근 삭제된 노드를 가져오고 노드에 있는 prev, next노드의 정보로 삽입을 수행.

1-3 노드에서 2 노드를 되돌리기 수행할 경우 1 노드의 next를 2 노드로, 3 노드의 prev를 3 노드로 해준다.

*삭제와 마찬가지로 root, tail노드 확인하고 업데이트 필요함

 

 

답 출력 시에는 0~N-1인 덱스와 탐색 중인 현재 노드의 data값이 일치하면 "O" 틀리면 "X"를 답에 더한다.

 

 

import java.util.Stack;

class Solution {
    public String solution(int n, int k, String[] cmd) {
		Stack<Node> zNode = new Stack<>();
		Node root = new Node(0);
		Node curNode = root;
		for (int i = 1; i < n; i++) {
			Node node = new Node(i);
			curNode.next = node;
			node.prev = curNode;
			curNode = node;
		}
        //root tail 서로 연결 - 순환구조처럼
		Node tail = curNode;
		root.prev = tail;
		tail.next = root;
		curNode = root;
        
        //처음 선택된 노드로 curNode 업데이트 
		while (k-- > 0) {
			curNode = curNode.next;
		}
		
		for (int i = 0; i < cmd.length; i++) {
			String[] s = cmd[i].split(" ");
			if (s.length == 1) {
				if (s[0].equals("C")) {//삭제C
					curNode.prev.next = curNode.next;
					curNode.next.prev = curNode.prev;
					zNode.push(curNode);
                    //root가 삭제될경우 next노드가 root노드가됨
					if (curNode == root) {
						root = curNode.next;
						curNode = root;  
					}
                    //tail노드가 삭제될 경우 prev노드가 tail노드가됨 
                    else if (curNode == tail) {
						tail = curNode.prev;
						curNode = tail;
					}else {
						curNode = curNode.next;
					}
				} else {//되돌리기Z
					Node node = zNode.pop();
					Node tmp = node.prev.next;
					node.prev.next = node;
					tmp.prev = node;
                    //되돌리고 난 후 root,tial 확인해서 업데이트
					if(node.data < root.data)
						root = node;
					else if(node.data > tail.data)
						tail = node;
				}
			} else {
				int num = Integer.parseInt(s[1]);
				if (s[0].equals("U")) {//위로이동U
					while (num-- > 0) {
						curNode = curNode.prev;
					}
				} else {//아래로이동D
					while (num-- > 0) {
						curNode = curNode.next;
					}
				}
			}
		}
		StringBuilder ans = new StringBuilder();
		
		for (int i = 0; i < n; i++) {
			if(root.data == i) {
				ans.append("O");
				root=root.next;
			}
			else {
				ans.append("X");
			}
		}
        return ans.toString();

	} 

	static class Node {
		Node prev;
		Node next;
		int data;

		Node(int data) {
			this.data = data;
			prev = null;
			next = null;
		}
	}

}