Menu

Subscribe

[JAVA/프로그래머스] 2019 KAKAO BLIND RECRUITMENT : 길 찾기 게임

HEESOO on Programmers

👀 문제

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

👊 도전

1. 설계

  1. x, y, value를 가지는 Node로 바꾸어 배열에 저장한 후, y 기준으로 내림차순 정렬한다. y가 같다면 x가 더 작은 것이 앞으로 온다.
  2. Node의 left, right를 이용하여 트리를 만든다.
  3. 전위 순회와 후위 순회를 진행한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public int[][] solution(int[][] nodeinfo) {
		Node[] array=new Node[nodeinfo.length];
		for(int i=0;i<nodeinfo.length;i++) {
			array[i]=new Node(nodeinfo[i][0], nodeinfo[i][1], i+1);
		}
		Arrays.sort(array, new Comparator<Node>(){
            @Override
            public int compare(Node o1, Node o2){
                if(o1.y<o2.y) return 1;
                else if(o1.y==o2.y){
                    if(o1.x<o2.x) return -1;
                    else return 1;
                }
                else return -1;
            }
        });
		Node root=array[0];
		for(int i=1;i<array.length;i++) {
			insert(root, array[i]);
		}
		int[][] answer=new int[2][array.length];
		ArrayList<Integer> result=new ArrayList<>();
		preorder(root, result);
		for(int i=0;i<result.size();i++) {
			answer[0][i]=result.get(i);
		}
		result.clear();
		postorder(root, result);
		for(int i=0;i<result.size();i++) {
			answer[1][i]=result.get(i);
		}
        return answer;
    }
	
	public void insert(Node root, Node node) {
		if(root.x>node.x) {
			if(root.left!=null) insert(root.left, node);
			else root.left=node;
		}
		else {
			if(root.right!=null) insert(root.right, node);
			else root.right=node;
		}
	}
	
	public void preorder(Node node, ArrayList<Integer> result) {
		result.add(node.value);
		if(node.left!=null) preorder(node.left, result);
		if(node.right!=null) preorder(node.right, result);
	}
	
	public void postorder(Node node, ArrayList<Integer> result) {
		if(node.left!=null) postorder(node.left, result);
		if(node.right!=null) postorder(node.right, result);
		result.add(node.value);
	}
}
class Node{
    int x;
    int y;
    int value;
    Node left;
    Node right;
    public Node(int x, int y, int v){
        this.x=x;
        this.y=y;
        this.value=v;
        this.left=null;
        this.right=null;
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. Node 클래스를 만든 후 배열에 넣어 정렬한다
    • x, y는 각 좌표, value는 노드 값이다.
    • left, right를 통해 자식 노드와 연결한다.
    • Comparator을 이용하여 정렬한다.
    • 중위 순회한 값 순서대로 저장되도록, y의 값이 클 수록 앞으로 온다. y가 같다면 x가 작은 것이 앞으로 온다.
  2. 트리를 만든다
    • insert()를 통해 트리를 만든다. root는 현재 내 위치이고, node는 새로 삽입할 값이다.
    • 현재 root보다 node의 x가 작다면 재귀를 통해 root의 left로 간다. 반대라면 right로 간다.
    • 가야할 곳이 null이라면 그 곳에 node를 넣는다.
  3. 전위순회와 후위순회를 하여 결과를 저장한다
    • 전위 순회는 preorder에서, 후위 순회는 postorder에서 한다.
    • 결과를 result에 저장하기 위해 ArrayList를 파라미터로 계속 넘겨준다.
    • result에 값이 들어오면 answer에 넣는다.

👏 해결 완료!

참고