[프로그래머스] 종이접기 (Java)

프로그래머스 종이접기

문제풀이

문제를 읽고나서 감이 전혀 잡히지 않아서 당황스러웠다. 하지만 예제를 바탕으로 규칙성을 찾으려고 노력한 결과 간단하게 풀어낼 수 있었다.

처음에는 0, 1로 되어있어서 비트연산을 사용하나? 하는 생각도 해보았으나 어림도 없는 생각이였다. 실마리를 찾기위해 우선 접는 횟수와 생기는 접힌 선의 갯수의 상관관계를 찾아보려고 했다. 하지만 찾지못했고 접히는 과정을 유심히 보다가 다른 규칙을 찾아냈다.

• 처음 접는 선은 무조건 0이다.
• 이전에 접힌 선들의 왼쪽에는 0 오른쪽에는 1의 선이 새로 접힌다.

이전에 접힌 선들에서 무조건 두 개의 선이 새로 접히는 것이였다. 여기까지 찾아내니 바로 완전이진트리가 떠올랐다. 완전이진트리를 상정하고 다시 예제들을 보니 완벽하게 들어맞았다. 또한 접는 횟수와 생기는 접힌 선의 갯수의 상관관계는 트리의 높이와 총 노드의 갯수와 같은 것이였다.

다음으로 정답으로 리턴하는 배열은 어떤 순서인가를 고민하였는데 왼쪽부터 차례로 담아야하는데 생각해보니 In-Order 순회랑 같았다.

• 완전이진트리를 만든다.
  • 배열의 길이(전체 노드의 수)는 (2^트리의 높이 - 1) + 1 이다. 마지막 +1은 배열의 인덱스를 1부터 시작하기 위함이다.
• 완전이진트리를 채운다.
  • 트리의 총 높이 - 1 높이에 존재하는 가장 오른쪽 노드까지 반복문을 수행하며 좌, 우 자식들에게 0, 1의 값을 넣는다.
  • 현재 트리의 높이보다 1작은 높이의 총 노드 갯수를 구하면 트리의 총 높이 - 1 높이에 존재하는 가장 오른쪽 노드의 인덱스를 구할 수 있다.
• 트리를 In-Order 순회한다.

구현코드

import java.util.*;

class Solution {
	  public int[] solution(int n) {
	      int[] binaryTree = new int[(int) Math.pow(2, n)];
	      ArrayList<Integer> ans = new ArrayList<>();
	      
	      binaryTree[1] = 0;
	      for(int i = 1 ; i < (int) Math.pow(2, n - 1) ; ++i) {
	    	  binaryTree[i * 2] = 0;
	    	  binaryTree[i * 2 + 1] = 1;
	      }
	    
	      inOrder(binaryTree, 1, ans);
	      
	      int[] answer = new int[ans.size()];
	      for(int i = 0 ; i < answer.length ; ++i) {
	    	  answer[i] = ans.get(i);
	      }
	      
	      return answer;
	  }
	  
	  private void inOrder(int[] binaryTree, int idx, ArrayList<Integer> ans) {
		  if(idx * 2 < binaryTree.length) inOrder(binaryTree, idx * 2, ans);
		  ans.add(binaryTree[idx]);
		  if(idx * 2 + 1 < binaryTree.length) inOrder(binaryTree, idx * 2 + 1, ans);
	  }
}