[프로그래머스] 길 찾기 게임 (자바)

 

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

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

정답률 약 7.4% 문제입니다.

문제를 읽었을 때 너무 헷갈렸습니다.

이해가 되려고 하면 라이언의 의도를 알아차렸다 하고, 다시 알 것 같으면 그럴 생각이 없다 하고...

이것들은 그냥 이야기였습니다..

 

문제는 이진트리를 구성하여 preorder와 postorder를 각각 진행하면 됩니다.

단, 주어진 좌표 값을 y축 기준으로 정렬하고 순서대로 트리에 삽입하면 됩니다.

 

트리의 삽입 과정에서 놓친 것이 하나 있었는데, 왼쪽으로 갔다가 오른쪽으로 갔다가 자유롭게 움직이며 추가할 수 있어야 합니다. 이것을 생각 못 해서 무조건 왼쪽, 무조건 오른쪽만 가도록 코드를 작성했고 디버깅에 꽤 오랜 시간이 걸렸네요.

 

코드 보며 이해할게요.

---

전역 변수

pre [], post [] = preorder, postorder의 결과를 저장하는 배열

index, jndex = 위의 배열에 값을 넣기 위한 인덱스

메소드

int [][] solution

list에 주어진 좌표 값을 Node형태로 저장합니다.

이 list를 y를 기준으로 내림차순 정렬을 합니다. 그래야 위에서부터 트리의 삽입이 가능합니다.

정렬된 Node들을 tree에 삽입하고 preorder와 postorder를 진행합니다.

(insert, preOrder, postOrder 호출)

 

class Tree

root를 가지는 트리입니다.

 

void insert

파라미터로 주어진 Node를 적절한 위치에 삽입합니다.

여기서 좌, 우로 자유롭게 움직일 수 있도록 while을 사용했습니다.

 

void preOrder

전위 순회합니다. V-L-R

 

void postOrder

후위 순회합니다. L-R-V

 

import java.util.*;

public class pm길찾기게임 {

	public int pre[], post[], index, jndex;

	public int[][] solution(int[][] nodeinfo) {
		Tree tree = new Tree();
		LinkedList<Node> list = new LinkedList<Node>();

		for(int i = 0; i < nodeinfo.length; i++) 
			list.add(new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]));

		pre = new int[list.size()];
		post = new int[list.size()];
		index = 0;
		jndex = 0;

		Collections.sort(list, new Comparator<Node>() {
			public int compare(Node n1, Node n2) {
				return n2.y-n1.y;
			}
		});

		for(int i = 0; i < list.size(); i++) 
			tree.insert(list.get(i));

		tree.preOrder(tree.root);
		tree.postOrder(tree.root);  	

		int[][] answer = {pre, post};
		return answer;
	}

	class Tree {
		Node root;

		Tree() {
			root = null;
		}

		void insert(Node newNode) {
			Node node = root;
			if(root == null)
				root = newNode;

			else {
				while(true) {
					boolean finish = true;
					while(node.left != null && node.x > newNode.x && node.y > newNode.y) {
						node = node.left;
						finish = false;
					}

					while(node.right != null && node.x < newNode.x && node.y > newNode.y) {
						node = node.right;
						finish = false;
					}
					if(finish)
						break;
				}

				if(node.x > newNode.x)
					node.left = newNode;
				else
					node.right = newNode;
			}
		}

		void preOrder(Node node) {
			if(node == null)
				return;
			pre[index++] = node.number;
			preOrder(node.left);
			preOrder(node.right);
		}

		void postOrder(Node node) {
			if(node == null)
				return;
			postOrder(node.left);
			postOrder(node.right);
			post[jndex++] = node.number;
		}
	}

	class Node {
		int number;
		int x, y;
		Node left, right;

		Node(int number, int x, int y) {
			this.number = number;
			this.x = x;
			this.y = y;
			left = null;
			right = null;
		}
	}

}