백준 9934, 완전 이진 트리 - Tree, Recursive / Queue

김은성·2022년 1월 28일
data structurequeuerecursionrecursivetree백준 9934 완전 이진 트리알고리즘자료구조재귀함수코딩 테스트큐트리
1

알고리즘

목록 보기
19/104

https://www.acmicpc.net/problem/9934


풀이 ① - Tree + 재귀 함수

배열 int[] tree에 트리 노드들 저장

1. 아이디어

  • 중위 순회 순서에서 루트 노드: 중간에 방문
    1) 루트 노드

    • 총 노드 개수 (2^k - 1) / 2 번째에 방문한 노드가 루트 노드
    • inorder[(2^k - 1) / 2]가 루트 노드인 tree[1]이 됨

    2) 찾은 부모 노드를 기준으로, Left / Right Subtree 각각에서 부모 노드찾음

    • 찾은 부모 노드가 [i]이면
      => Left Subtree 에서의 부모 노드는 [0] ~ [i-1]의 중간 index
      => Right Subtree 에서의 부모 노드는 [i+1] ~ [끝]의 중간 index

      이분 탐색(Binary Search) 하듯이 중간 index(부모) 기준으로 2개 Subtree

  • recursive(startIdx, endIdx)로 중위 순회에서 부모 index 찾음
    => 재귀 종료 조건: Leaf 노드까지 내려간 경우

  • 트리에서 부모 index 가 [i] 이면 (루트 노드는 [1])

    • Left Child: [i * 2]
    • Right Child: [i * 2 + 1]



2. 자료구조

  • int[]: 입력 값, 중위 순회 순서 저장
    => [0 ~ ] 사용
  • int[]: 출력 값, 트리 저장
    => [1 ~ ] 사용



3. 시간 복잡도

  • 1개 부모 노드에서 재귀 호출 2번 수행
    => 전체 (2^k - 1)개 노드에서, 대충 총 2(2^k - 1) 번 재귀 호출 발생
    => k 최대값 대입: 2(2^10 - 1) = 2(1,024 - 1) = 2,046 << 1억 (1초)



코드

import java.io.*;
import java.util.StringTokenizer;

public class Main_Recursive1 {
	static int k;			// 완전 이진 트리의 depth
	static int nodeCount;		// 총 노드 개수: 2^k - 1
	static int[] inorder;		// 입력: Inorder Traversal (중위 순회) 방문 순서
	static int[] tree;		// 출력: 트리 (루트 노드: tree[1])

	/* startIdx, endIdx: 중위 순회 순서 inorder[]에서의 index */
	/* treeIdx: 출력 배열 tree[]에 채울 index */
	static void recursive(int startIdx, int endIdx, int treeIdx) {
		// 주어진 범위 start ~ end 에서, 중위 순회 inorder[] 의 부모 노드를 찾음
		int parentIdx = (startIdx + endIdx) / 2;
		tree[treeIdx] = inorder[parentIdx];

		int leftChildIdx = treeIdx * 2;
		int rightChildIdx = treeIdx * 2 + 1;

		// 재귀 종료 조건: Leaf 노드까지 내려간 경우
		if (startIdx == endIdx)
			return;

		recursive(startIdx, parentIdx - 1, leftChildIdx);	// left subtree
		recursive(parentIdx + 1, endIdx, rightChildIdx);	// right subtree
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		k = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		nodeCount = (int)Math.pow(2, k) - 1;
		inorder = new int[nodeCount];		// [0 ~ 노드 개수 - 1] 사용
		tree = new int[nodeCount + 1];		// [1 ~ 노드 개수] 사용
		for (int i = 0; i < inorder.length; i++)
			inorder[i] = Integer.parseInt(st.nextToken());

		// 루트 노드 tree[1] 에서부터 시작
		recursive(0, nodeCount - 1, 1);

		// 트리의 Depth (Level) 단위로 개행하여 출력
		StringBuilder sb = new StringBuilder();
		for (int level = 1; level <= k; level++) {
			// 현재 level 까지 속하는 노드 개수
			// e.g. level 2 까지 => 2^2 - 1 = 3개
			int currentNodeCount = (int)Math.pow(2, level) - 1;
			int prevNodeCount = (int)Math.pow(2, level - 1) - 1;

			for (int i = prevNodeCount + 1; i <= currentNodeCount; i++)
				sb.append(tree[i]).append(" ");
			sb.append("\n");
		}
		System.out.println(sb);
	}
}





풀이 ② - Tree + 재귀 함수

트리 Level 단위로 StringBuilder[]에 저장 (Level Order Traversal)

1. 아이디어

  • 중위 순회 순서에서 루트 노드: 중간에 방문
    1) 루트 노드

    • 총 노드 개수 (2^k - 1) / 2 번째에 방문한 노드가 루트 노드
    • inorder[(2^k - 1) / 2]가 루트 노드인 tree[1]이 됨

    2) 찾은 부모 노드를 기준으로, Left / Right Subtree 각각에서 부모 노드찾음

    • 찾은 부모 노드가 [i]이면
      => Left Subtree 에서의 부모 노드는 [0] ~ [i-1]의 중간 index
      => Right Subtree 에서의 부모 노드는 [i+1] ~ [끝]의 중간 index

      이분 탐색(Binary Search) 하듯이 중간 index(부모) 기준으로 2개 Subtree

  • recursive(startIdx, endIdx)로 중위 순회에서 부모 index 찾음
    => 재귀 종료 조건: Leaf 노드까지 내려간 경우

  • 트리에서 부모 index 가 [i] 이면 (루트 노드는 [1])

    • Left Child: [i * 2]
    • Right Child: [i * 2 + 1]



2. 자료구조

  • int[]: 입력 값, 중위 순회 순서 저장
    => [0 ~ ] 사용
  • StringBuilder[]: 출력 값, 트리 Level 단위로 노드들 저장



3. 시간 복잡도

  • 1개 부모 노드에서 재귀 호출 2번 수행
    => 전체 (2^k - 1)개 노드에서, 대충 총 2(2^k - 1) 번 재귀 호출 발생
    => k 최대값 대입: 2(2^10 - 1) = 2(1,024 - 1) = 2,046 << 1억 (1초)



코드

import java.io.*;
import java.util.StringTokenizer;

public class Main_Recursive2 {
	static int k;			// 완전 이진 트리의 depth
	static int nodeCount;		// 총 노드 개수: 2^k - 1
	static int[] inorder;		// 입력: Inorder Traversal (중위 순회) 방문 순서
	static StringBuilder[] sbArr;
	// 출력: 트리 Level 단위로 노드들 저장
	// e.g. sbArr[1] => Level 1 루트 노드

	/* startIdx, endIdx: 중위 순회 순서 inorder[]에서의 index */
	/* level: 트리의 level, 저장할 StringBuilder[] 의 index */
	static void recursive(int startIdx, int endIdx, int level) {
		// 재귀 종료 조건: Leaf 노드까지 내려간 경우
		if (level > k)
			return;

		int parentIdx = (startIdx + endIdx) / 2;
		sbArr[level].append(inorder[parentIdx]).append(" ");

		recursive(startIdx, parentIdx - 1, level + 1);	// left subtree
		recursive(parentIdx + 1, endIdx, level + 1);	// right subtree
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		k = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		nodeCount = (int)Math.pow(2, k) - 1;
		inorder = new int[nodeCount];			// [0 ~ 노드 개수 - 1] 사용
		sbArr = new StringBuilder[nodeCount + 1];	// [1 ~ 노드 개수] 사용
		for (int i = 1; i < sbArr.length; i++)
			sbArr[i] = new StringBuilder();
		for (int i = 0; i < inorder.length; i++)
			inorder[i] = Integer.parseInt(st.nextToken());

		// Level 1, 루트 노드에서부터 시작
		recursive(0, nodeCount - 1, 1);

		// 트리의 Depth (Level) 단위로 개행하여 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < sbArr.length; i++)
			sb.append(sbArr[i]).append("\n");
		System.out.println(sb);
	}
}





풀이 ③ - Tree + Queue

트리의 Level 단위로 Queue에 노드 추가 (Level Order Traversal)

1. 아이디어

  • 중위 순회 순서에서 루트 노드: 중간에 방문
    1) 루트 노드

    • 총 노드 개수 (2^k - 1) / 2 번째에 방문한 노드가 루트 노드
    • inorder[(2^k - 1) / 2]가 루트 노드인 tree[1]이 됨

    2) 찾은 부모 노드를 기준으로, Left / Right Subtree 각각에서 부모 노드찾음

    • 찾은 부모 노드가 [i]이면
      => Left Subtree 에서의 부모 노드는 [0] ~ [i-1]의 중간 index
      => Right Subtree 에서의 부모 노드는 [i+1] ~ [끝]의 중간 index

      이분 탐색(Binary Search) 하듯이 중간 index(부모) 기준으로 2개 Subtree

  • 트리에서 부모 index 가 [i] 이면 (루트 노드는 [1])

    • Left Child: [i * 2]
    • Right Child: [i * 2 + 1]



2. 자료구조

  • int[]: 입력 값, 중위 순회 순서 저장
    => [0 ~ ] 사용
  • Queue<Pair>, LinkedList<Pair>: 트리 Level 단위로 inorder[]에서 탐색할 Pair (startIdx, endIdx) 저장



3. 시간 복잡도



코드

import java.io.*;
import java.util.*;


class Pair {
	public int startIdx, endIdx;

	public Pair(int startIdx, int endIdx) {
		this.startIdx = startIdx;
		this.endIdx = endIdx;
	}
}

public class Main_Queue {
	static int k;			// 완전 이진 트리의 depth
	static int nodeCount;		// 총 노드 개수: 2^k - 1
	static int[] inorder;		// 입력: Inorder Traversal (중위 순회) 방문 순서

	static StringBuilder sb = new StringBuilder();	// 출력 값: 트리의 Level 단위로 노드들 저장
	static Queue<Pair> queue = new LinkedList<>();	// 트리의 Level 단위로 노드들을 Queue 에 추가

	static void solution() {
		while (!queue.isEmpty()) {
			// 현재 트리 Level 의 노드 개수
			int currentNodeCount = queue.size();
			for (int i = 0; i < currentNodeCount; i++) {
				Pair p = queue.remove();

				int parentIdx = (p.startIdx + p.endIdx) / 2;
				sb.append(inorder[parentIdx]).append(" ");

				// p.startIdx == p.endIdx 인 경우, Leaf 노드까지 내려감
				if (p.startIdx != p.endIdx) {
					queue.add(new Pair(p.startIdx, parentIdx - 1));	// left subtree
					queue.add(new Pair(parentIdx + 1, p.endIdx));	// right subtree
				}
			}

			sb.append("\n");
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		k = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		nodeCount = (int)Math.pow(2, k) - 1;
		inorder = new int[nodeCount];		// [0 ~ 노드 개수 - 1] 사용
		for (int i = 0; i < inorder.length; i++)
			inorder[i] = Integer.parseInt(st.nextToken());

		// 루트 노드에서부터 시작
		queue.add(new Pair(0, nodeCount - 1));
		solution();

		System.out.println(sb);
	}
}
profile
김은성
Silver Star
이전 포스트

백준 1991, 트리 순회 - Tree, Recursive

다음 포스트

백준 1167, 트리의 지름 - Tree, DFS

0개의 댓글