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

 

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

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

 

문제 요약

• 입력받은 int[][] nodeinfo를 통해 이진 트리를 생성하고, 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return하는 문제
• nodeinfo[i]는 { x좌표, y좌표 } 로 구성

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

 

문제 풀이

*  이진 트리, 정렬

-  nodeinfo 탐색  =>  i 번째의 x 좌표( nodeinfo[i][0] ), y 좌표( nodeinfo[i][1] )에서
   -  x 좌표  ☞  노드의 값
   -  y 좌표  ☞  노드의 레벨  ( 여기서는 레벨이 높을수록 상위 노드 )
   -  i+1  ☞  노드의 번호

-  x, y, i+1 을 묶어 노드들의 배열 생성 ( int형 2차원 배열 생성 or 'Node' 클래스 정의 후 객체 배열 생성 )

-  노드 배열( int nd[][] or Node nd[] )을 y 기준 내림차순, x 기준 오름차순 정렬

-  TreeNode 클래스 생성
   -  멤버 변수
      -  현재 노드의 값( v : val )
      -  현재 노드의 번호( n : num )
      -  현재 노드의 왼쪽 자식 노드( l : left )
      -  현재 노드의 오른쪽 자식 노드( r : right )
      -  현재 노드의 부모 노드( p : parent )
   -  멤버 함수
      -  생성자( TreeNode() )
      -  설정자 - 왼쪽 자식 노드( setLeftChild() )
      -  설정자 - 오른쪽 자식 노드( setRightChild() )
      -  노드 삽입( addNode() )
      -  전위 순회( preOrder() )
      -  후위 순회( postOrder() )

-  이진 트리의 루트 노드( R )는 노드 배열의 첫 번째 노드이다( nd[0] )

-  노드 배열( nd[][] )을 탐색하며 루트 노드에 차례로 노드의 값과 번호를 삽입
  ( 노드 삽입 -- 삽입하려는 노드의 값이 현재 노드의 값보다 작으면 왼쪽 서브 트리에, 크면 오른쪽 서브 트리에 넣음 )

-  생성된 이진 트리를 전위/후위 순회
  ( 전위 순회 : 루트 노드 -> 왼쪽 서브 노드 -> 오른쪽 서브 노드 )
  ( 후위 순회 : 왼쪽 서브 노드 -> 오른쪽 서브 노드 -> 루트 노드 )

import java.util.Arrays;

public class Solution {
	
	int trvs[][], idx;
	
	class TreeNode {
		int v, n;  // x, i 
		TreeNode l, r, p;
		TreeNode( int v, int n ) {
			this.v = v;
			this.n = n;
		}
		public void setLeftChild( TreeNode l ) {
			this.l = l;
			if( l != null ) 
				l.p = this;
		}
		public void setRightChild( TreeNode r ) {
			this.r = r;
			if( r != null ) 
				r.p = this;
		}
		public void addNode( TreeNode c, int v, int n ) {  // insert
			TreeNode l = c.l, r = c.r;
			if( v < c.v ) {
				if( l == null )
					c.setLeftChild( new TreeNode( v, n ) );
				else				
					addNode( l, v, n );
			}
			else {
				if( r == null )	
					c.setRightChild( new TreeNode( v, n ) );
				else				
					addNode( r, v, n );
			}
		}
		public void preOrder( TreeNode c ) {  // traversal
			if( c != null ) {
				trvs[0][idx++] = c.n;
				preOrder( c.l );
				preOrder( c.r );
			}
		}
		public void postOrder( TreeNode c ) {  // traversal
			if( c != null ) {
				postOrder( c.l );
				postOrder( c.r );
				trvs[1][idx++] = c.n;
			}
		}
	}
	
	public int[][] solution( int[][] nodeinfo ) {
		int n = nodeinfo.length, i;
		int nd[][] = new int[n][3];
		for( i = 0; i < n; i++ ) {
			nd[i][0] = nodeinfo[i][0];
			nd[i][1] = nodeinfo[i][1];
			nd[i][2] = i+1;
		}
		Arrays.sort( nd, ( n1, n2 ) -> { return n1[1]==n2[1] ? n1[0]-n2[0] : n2[1]-n1[1]; } );
		TreeNode R = new TreeNode( nd[0][0], nd[0][2] );
		for( i = 1; i < n; i++ )
			R.addNode( R, nd[i][0], nd[i][2] );
		trvs = new int[2][n];  // pre/post_order_traversal
		idx = 0;  
		R.preOrder( R );
		idx = 0; 
		R.postOrder( R );
		return trvs;
	}
}