[프로그래머스 2019 KAKAO BLIND RECRUITMENT] 길 찾기 게임 -Java

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

코딩테스트 연습 - 길 찾기 게임

import java.util.*;
class Solution {
		class Node {
			int x, y, no;
			Node left, right;

			public Node(int x, int y, int no, Node left, Node right) {
				super();
				this.x = x;
				this.y = y;
				this.no = no;
				this.left = left;
				this.right = right;
			}
		}

		public int[][] solution(int[][] nodeinfo) {
			int[][] answer = new int[2][nodeinfo.length];

			List<int[]> nodeInfoList = new ArrayList<>();

			inputNodeInfo(nodeinfo, nodeInfoList);

			int[] rootNode = nodeInfoList.get(0);
			Node root = new Node(rootNode[0], rootNode[1], rootNode[2], null, null);

			for (int i = 1; i < nodeInfoList.size(); i++) {
				int[] node = nodeInfoList.get(i);
				connectNode(root, node);
			}

			List<Integer> pre = new ArrayList<>();
			List<Integer> post = new ArrayList<>();
			preorder(root, pre);
			postorder(root, post);
			result(answer,pre,post);
			return answer;
		}

		private void result(int[][] answer, List<Integer> pre, List<Integer> post) {
			for(int i=0; i<answer[0].length; i++) {
				answer[0][i]=pre.get(i);
				answer[1][i]=post.get(i);
			}
		}

		private void postorder(Node root, List<Integer> post) {
			if (root == null) return;
			postorder(root.left, post);
			postorder(root.right, post);
			post.add(root.no);

		}

		private void preorder(Node root, List<Integer> pre) {
			if (root == null)  return;
			pre.add(root.no);
			preorder(root.left, pre);
			preorder(root.right, pre);

		}

		private void inputNodeInfo(int[][] nodeinfo, List<int[]> nodeInfoList) {
			for (int i = 0; i < nodeinfo.length; i++) {
				int x = nodeinfo[i][1];
				int y = nodeinfo[i][0];
				int no = i + 1;
				nodeInfoList.add(new int[] { x, y, no });
			}
			Collections.sort(nodeInfoList, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					if (o1[0] == o2[0])
						return o1[1] - o2[1];
					return o2[0] - o1[0];
				}
			});
		}

		private void connectNode(Node root, int[] node) {

			if (root.y > node[1]) { // 자식 노드가 왼쪽에
				if (root.left == null) { // 현재 노드의 오른쪽이 비어있으면
					root.left = new Node(node[0], node[1], node[2], null, null);// 오른쪽 연결
				} else { // 왼쪽 자식이 이미 있다면 다음으로 넘겨줌
					connectNode(root.left, node);
				}
			} else { // 자식 노드가 왼쪽에 붙어야 함
				if (root.right == null) { // 현재 노드의 오른쪽이 비어있으면
					root.right = new Node(node[0], node[1], node[2], null, null);// 오른쪽 연결
				} else { // 오른쪽 자식이 이미 있다면 다음으로 넘겨줌
					connectNode(root.right, node);
				}
			}

		}
	}

소요시간 : 1시간

 

문제를 읽어보면 이진트리를 만들고 preorder, postorder을 돌려라 라는 뜻입니다.(제가 생각하기에는..ㅎ)

 

그래서 우선 이진트리를 만들어주었습니다.

Node클래스를 통해 노드를 관리하였습니다.

 

그리고 저는 문제에서 x, y를 바꿔서 풀었습니다. 문제에는 x, y가 서로 바뀌어 있어서 헷갈리더라고요..

 

이진트리를 만들기 위해서 가장 먼저 해야 하는 일은 각 노드의 좌표를 정렬하는 일입니다.

 

문제를 잘 보시면 (제가 바꾼 좌표 기준) x가 크고, y가 작은 순으로 정렬을 하게 되면

요거를 하나씩 뽑으면서 바로 트리를 만들 수 있습니다~

 

요렇게 정렬을 끝낸 뒤에는 y좌표를 기준으로 트리를 만들어줍니다.

 

트리를 다 만들었다면?

preorder, postorder을 돌려주면 끝납니다

 

preoreder은 전위 순회인 거 아시죠? 

현재 자신의 노드를 출력하고, 왼쪽, 오른쪽 노드 순으로 들어가게 됩니다.

 

postorder은 후위 순회입니다

자신의 노드 기준 왼쪽, 오른쪽으로 끝가지 들어간 다음 출력을 해주면 됩니다.

 

끝~