[프로그래머스/자바] 길 찾기 게임 풀이 - 2019 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2019 KAKAO BLIND RECRUITMENT Level 3 문제다.

 

 

 

    	for(int i=0;i<n;i++) 
    		nodes.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
            
    	nodes.sort((o1, o2) -> o1.y == o2.y ? o1.x - o2.x : o2.y - o1.y);

먼저 nodeinfo에 있는 노드들을 Node의 객체로 생성해 ArrayList nodes에 넣어준다.

Node들이 담긴 nodes를 y가 큰 순서대로, y가 같다면 x가 작은 순서대로 정렬한다.

레벨이 높은 순서대로 정렬되기 때문에 nodes의 가장 첫 번째 node가 root 노드가 된다.

 

 

    static void setChild(Node node, ArrayList<Node> list) {
    	ArrayList<Node> left = new ArrayList<>();
    	ArrayList<Node> right = new ArrayList<>();
    	
    	for(int i=1;i<list.size();i++) {
    		Node next = list.get(i);
    		if(next.x < node.x)
    			left.add(next);
    		else
    			right.add(next);
    	}

한 노드의 왼쪽, 오른쪽 자식 노드를 결정하는 setChild 함수에 root 노드, nodes를 전달한다. 

즉 setChild 함수의 첫 번째 매개변수는 자식 노드를 결정할 타겟 노드, 두 번째 매개변수는 그 노드보다 하위 노드들이 담겨있는 ArrayList다.

 

 

 

    	Node leftNode = left.size() == 0 ? null : left.get(0);
    	Node rightNode = right.size() == 0 ? null : right.get(0);
    	
    	node.left = leftNode;
    	node.right = rightNode;
    	if(leftNode != null)
    		setChild(leftNode, left);
    	if(rightNode != null)
    		setChild(rightNode, right);

 

ArrayList의 Node들을 하나씩 탐색하며 타겟 노드보다 왼쪽에 있다면 left, 오른쪽에 있다면 right에 넣는다.

(0번째부터 탐색하지 않고 1번째부터 탐색하는 이유는 0번째가 자기자신이기 때문에)

가장 처음에 nodes를 정렬했기 때문에 left와 right의 맨 처음 원소가 타겟 노드의 왼쪽 자식, 오른쪽 자식이 된다.

 

그리고 왼쪽 자식의 자식을 재귀적으로 찾아야 하기 때문에 왼쪽 자식 노드와 left를 가지고 setChild를 호출한다.

오른쪽도 마찬가지로 오른쪽 자식 노드와 right를 가지고 setChild를 호출한다.

이때 left, right에 아무것도 담겨있지 않다면 타겟 노드의 왼쪽/오른쪽 자식 노드가 존재하지 않는 것이므로 

setChild도 재귀적으로 호출하지 않는다.

 

 

 

리프 노드까지 모두 setChild를 수행했다면 전위 순회, 후위 순회를 통해 answer에 담아준다.

전위/후위 순회는 기본적인 내용이기 때문에 설명은 생략한다.

 

 

느낀점

코드 자체는 길이도 짧고 직관적이라 어렵지 않고 생각한다. 푸는 것도 쉬웠다.

하지만 최악의 경우 166ms가 나오기 때문에 (테케 9) 너무 비효율적으로 풀었다.

다른 분들 코드를 보니 left, right에 Node를 다 담는 것이 아닌 재귀로 풀 수 있다는 것을 알았다.

분명 트리 문제를 풀면서 비슷한 코드를 공부했던 것 같은데 활용하지 못한 점이 아쉽다.

 

 

 

 

전체 코드

import java.util.*;

class Solution {
	static int idx = 0;
	static ArrayList<Node> nodes = new ArrayList<>();
	static int[][] answer;
	
    static class Node {
    	int idx;
    	int x, y;
    	Node left, right;
    	
    	Node(int idx, int x, int y) {
    		this.idx = idx;
    		this.x = x;
    		this.y = y;
    	}
    }

    public int[][] solution(int[][] nodeinfo) {
    	int n = nodeinfo.length;
    	answer = new int[2][n];
    	
    	for(int i=0;i<n;i++) 
    		nodes.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
    	
    	nodes.sort((o1, o2) -> o1.y == o2.y ? o1.x - o2.x : o2.y - o1.y);
        
    	Node root = nodes.get(0);
    	setChild(root, nodes);
        
    	preOrder(root);
    	idx = 0;
    	postOrder(root);
    	
    	return answer;
    }
    
    static void preOrder(Node node) {
    	answer[0][idx++] = node.idx;
    	if(node.left != null) preOrder(node.left);
    	if(node.right != null) preOrder(node.right);
    }
    
    static void postOrder(Node node) {
    	if(node.left != null) postOrder(node.left);
    	if(node.right != null) postOrder(node.right);
    	answer[1][idx++] = node.idx;
    }
    
    static void setChild(Node node, ArrayList<Node> list) {
    	ArrayList<Node> left = new ArrayList<>();
    	ArrayList<Node> right = new ArrayList<>();
    	
    	for(int i=1;i<list.size();i++) {
    		Node next = list.get(i);
    		if(next.x < node.x)
    			left.add(next);
    		else
    			right.add(next);
    	}
    	
    	Node leftNode = left.size() == 0 ? null : left.get(0);
    	Node rightNode = right.size() == 0 ? null : right.get(0);
    	
    	node.left = leftNode;
    	node.right = rightNode;
    	if(leftNode != null)
    		setChild(leftNode, left);
    	if(rightNode != null)
    		setChild(rightNode, right);
    }
}