프로그래머스 - 표현 가능한 이진트리

필요지식

• 이진트리
• 트리순회

문제 설명

해당 수를 이진트리로 표현할 수 있으면 1 없으면 0을 출력하는 문제이다.

주어진 문제 예시를 보면 주어진 이진트리에 더미노드를 추가하여 포화 이진트리를 형성한다.

즉, 이 것을 이용해 이진트리로 만들 수 있는지 없는지를 판별하면 된다.

문제에는 포화이진트리를 만들수 있는지 없는지 이렇게 물어보지 않고 있다.

numbers 에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0

 

이진트리에 속해있는 것이 포화이진트리이다.

- 이진트리는 자식노드가 최대 2개인 트리이다.

- 포화이진트리는 이진트리이면서 모든 레벨이 노드로 꽉 차 있어야 한다.

그렇기 때문에 이 문제는 해당 수를 이진수로 표현하고 포화이진트리로 형태로 만들면서 이것이 이진트리가 될 수있는지 없는지 판별하는 문제이다.

 

 

주어진 숫자를 이진수로 바꿨을 때 포화이진트리로 만들기 위해 더미노드를 추가할 수 있다고 주어진다.

• 더미는 0 나머지는 1로 표현한다.

더미노드는 반드시 변환된 이진수 앞에만 추가해야한다.

- 왜냐하면 더미노드 0을 다른위치에 추가하게 되면 주어진 숫자가 바뀔 수 있기 때문이다.

- 더미노드를 언제까지 추가해야하냐면 각 이진수 자리가 2^n - 1이 될 때까지 더미를 추가해야한다.

 

포화 이진 트리는 반드시 2 ^ n -1 개의 노드를 갖기 때문이다.

만약 더미를 추가해서 포화이진트리를 만들 수 없는 경우에 대해서 살펴보면 주어진 테스트 케이스에 5는 포화이진트리를 구성할 수 없다.

왜냐하면 5는 이진수로 바꾸면 101 이것을 이진트리로 바꾸면 이렇게 표현된다.

                   0

1                                       1

왜 이진 트리가 101이 “왼쪽 노드 - 가운데 노드 - 오른쪽 노드 “ 로 되어지는 이유는 설명에서 주어진 포화이진트리의 문자를 생성하는 규칙을 번호로 기재하여 그것을 기반으로 문자열을 표현한 그림을 보면 알 수 있다.

이부분을 보면 중위 순회방식인 것을 알 수 있다.

숫자 5의 이진수 101 은 2^2 -1 길이를 갖기 때문에 더미를 추가하지 않았다. 설명 예시를 다시 보면 0이 부모인 경우는 없고 1로 표시된 부분만이 일반 노드로 표현되고 있다. 그리고 0은 더미노드로 취급되고 있다.

포화이진트리로 만들고 각 서브트리에 부모가 0이고 자식이 더미가 아닌 수가 존재하기만 하면 포화이진트리를 형성할 수 없어 이진트리가 아니게 된다.

중위순회인것을 알았으니 이제 중위 순회의 특징에 대해 알아야 한다.

중위순회에서 부모는 배열의 중앙 위치에 존재한다. 전체 이진수 자리 가운데 위치한 것이 부모 그 왼쪽 서브트리에서 가운데 위치한것이 부모의 자식이자 또다른 왼쪽 서브트리의 부모 역할을 하게 된다.

풀이

public int[] solution(long[] numbers) {
		List<Integer> answer = new ArrayList<>();

		for (long val : numbers) {
			String binary = Long.toBinaryString(val);
			int i = 0;
			while ((int)Math.pow(2, i) - 1 < binary.length()) {
				i++;
			}

			while((int)Math.pow(2, i)-1 != binary.length()) {
				binary = "0"+ binary;
			}

			if (isValid(binary)) {
				answer.add(1);
			} else {
				answer.add(0);
			}
		}

		return answer.stream()
			.mapToInt(v -> v)
			.toArray();
	}

	boolean isPossible = true;

	public boolean isValid(String binary) {
		isPossible=true;
		dfs(binary);

		return isPossible;
	}

	public void dfs(String str) {
		if (!isPossible) {
			return;
		}

		int midIdx = str.length() / 2;
		int root = str.charAt(midIdx);
		String left = str.substring(0, midIdx);
		String right = str.substring(midIdx + 1, str.length());
		// 모두 더미일수도 있음.
		// if (root == '0' && left.length() > 0 && right.length() > 0) {
		// 	isPossible = false;
		// 	return;
		// }

		if(root == '0' && (left.charAt(left.length()/2) =='1' || right.charAt(right.length()/2) =='1')){
			isPossible=false;
			return;
		}

		if (left.length() >=3) {
			dfs(left);
		}

		if (right.length() >=3) {
			dfs(right);
		}
	}