프로그래머스_종이접기_자바

 

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

코딩테스트 연습 - 종이접기

진행과정을 생각해보자

 

Step 1 :       0                  

Step 2 :     0 0 1            

Step 3 :  0 0 1 0 0 1 1

 

진행과정동안 배열 사이에 (0 1) 이 삽입된다. 

모양을 그려보면 완전 이진 트리가되고 왼쪽자식이 0 오른쪽자식이 1 이된다.

ex Step 3)

           0

        0     1

      0  1  0  1

 inorder 순회를 하면 Step 3 의정답이되고 다음 Step 은 위와 같은 규칙으로 트리의 높이가 1 늘어난다

 

즉 완전 이진 트리를 생성우 inorder 순회를 해주면 된다.

 

import java.util.*;
class Solution {
    static int[] binTree;
	static ArrayList<Integer> list;
 static int[] solution(int n) {
		  
		  binTree = new int[(int) Math.pow(2, n)];
		  list = new ArrayList<>();
		  
		  binTree[1] = 0;
		  // 트리생성
		  for(int i = 1; i < Math.pow(2, n - 1); i++) {
			  binTree[i * 2] = 0;
			  binTree[i * 2 + 1] = 1;
		  }
		  
		  inOrder(1);
		  int[] answer = new int[list.size()];
		  for(int i = 0; i < answer.length; i++) {
			  answer[i] = list.get(i);
		  }
		  
		  return answer;
	   }
	   // inorder 순회
	   static void inOrder(int index) {
		   if(index * 2 < binTree.length) inOrder(index * 2);
		   list.add(binTree[index]);
		   if(index * 2 + 1 < binTree.length) inOrder(index * 2 + 1);
	   }
}