프로그래머스 길찾기 게임 (JAVA)

2020 KAKAO BLIND RECRUITMENT

---

길찾기 게임

---

 

지문 요약

라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

 

로직

이진탐색 문제이다. 코드는 굉장히 깔끔하게 구현할 수 있다. 크게 부연설명이 필요한 문제는 아니므로, 코드 전문을 첨부하겠습니다.

import java.util.*;

public class 길찾기게임 {
	static List<Node> nodes = new ArrayList<>();
	static Node root;
	static List<Integer> pre = new ArrayList<>();
	static List<Integer> post = new ArrayList<>();

	public static void main(String[] args) {
		int[][] nodeinfo = new int[][] { { 5, 3 }, { 11, 5 }, { 13, 3 }, { 3, 5 }, { 6, 1 }, { 1, 3 }, { 8, 6 },
				{ 7, 2 }, { 2, 2 } };
		System.out.println(solution(nodeinfo));
	}

	public static int[][] solution(int[][] nodeinfo) {
		for (int i = 0; i < nodeinfo.length; i++) {
			nodes.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
		}
		Collections.sort(nodes);
		root = nodes.get(0);
		for (int i = 1; i < nodes.size(); i++) {
			connectNode(root, nodes.get(i));
		}
		preOrder(root);
		postOrder(root);
		int[][] answer = new int[2][];
		answer[0] = pre.stream().mapToInt(i -> i).toArray();
		answer[1] = post.stream().mapToInt(i -> i).toArray();
		return answer;
	}

	private static void preOrder(Node now) {
		if (now != null) {
			pre.add(now.num);
			if (now.left != null) {
				preOrder(now.left);
			}
			if (now.right != null) {
				preOrder(now.right);
			}
		}
	}

	private static void postOrder(Node now) {
		if (now != null) {
			if (now.left != null) {
				postOrder(now.left);
			}
			if (now.right != null) {
				postOrder(now.right);
			}
			post.add(now.num);
		}
	}

	private static void connectNode(Node parent, Node child) {
		if (parent.x > child.x) {
			if (parent.left == null) {
				parent.left = child;
			} else {
				connectNode(parent.left, child);
			}
		} else {
			if (parent.right == null) {
				parent.right = child;
			} else {
				connectNode(parent.right, child);
			}
		}
	}

	static class Node implements Comparable<Node> {
		Node left;
		Node right;
		int num;
		int x;
		int y;

		Node(int num, int x, int y) {
			this.x = x;
			this.y = y;
			this.num = num;
		}

		@Override
		public int compareTo(Node o) {
			return o.y - this.y;
		}
	}

}