[SWEA] 1231. 중위순회

문제

1231. [S/W 문제해결 기본] 9일차 - 중위순회
제시된 완전 이진 트리를 in-order 형식으로 순회하여 읽어라.
그러면 단어가 된다.

풀이

1. 입력받기
트리의 부모-자식 정보는 tree배열에, 정점의 알파벳은 alpha배열로 나눠서 저장했다.

읽어야 할 데이터의 개수가 계속 달라져서 고민됐는데, <완전 이진 트리>라서 다행이었다.
정점의 수가 N개이므로, 다음과 같이 구분했다. (결과적으로 좋은 방법은 아니다.)

[1] 1 ~ N/2-1 번 정점 : 자식노드가 2개
[2] N/2번 정점 : 자식노드가 1개 또는 2개
[3] N/2+1 ~ N 번 정점 : 자식노드 없음

따라서 [1]번은 4개를 입력받고, [3]번은 2개를 입력받았다. [2]번은 N이 짝수이면 3개, 홀수이면 4개이므로 구분지었다.
(+ 길어져서 함수로 뺐다.)

static void input(int [][] tree, int N, Scanner sc) {
	int a;
	String b;
	int i;
	
	// [1] 4개
	for (i=1; i<N/2; i++) {
		a = sc.nextInt();
		b = sc.next();
		alpha[i] = b.charAt(0);
		a = sc.nextInt();
		tree[i][0] = a;
		a = sc.nextInt();
		tree[i][1] = a;
	}
	
	// [2] 3개 or 4개 
	a = sc.nextInt();
	b = sc.next();
	alpha[i] = b.charAt(0);
	a = sc.nextInt();
	tree[i][0] = a;
	if (N%2==1) { // 홀수일 때 
		a = sc.nextInt();
		tree[i][1] = a;
	}
	
	// [3] 2개
	i++;
	for (; i<=N; i++) {
		a = sc.nextInt();
		b = sc.next();
		alpha[i] = b.charAt(0);
	}
}

2. in-order
in-order 방식으로 그때그때 노드의 문자를 출력했다.

static void inOrder(int [][] tree, int cur) {
	child(tree, 0, cur); // 왼쪽 자식
	System.out.print(alpha[cur]); // 정점의 알파벳 출력
	child(tree, 1, cur); // 오른쪽 자식
}

static void child(int [][] tree, int flag, int cur) {
	if (tree[cur][flag] == 0) return;
	inOrder(tree, tree[cur][flag]);
}

자바코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{	
	static char [] alpha = new char[101];
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = 10;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = sc.nextInt();
			int [][] tree = new int[N+1][2];
			input(tree, N, sc);
			
			System.out.printf("#%d ", test_case);
			inOrder(tree, 1);
			System.out.println();
		}
	}
	
	static void inOrder(int [][] tree, int cur) {
		child(tree, 0, cur);
		System.out.print(alpha[cur]);
		child(tree, 1, cur);
	}
	
	static void child(int [][] tree, int flag, int cur) {
		if (tree[cur][flag] == 0) return;
		inOrder(tree, tree[cur][flag]);
	}
	
	static void input(int [][] tree, int N, Scanner sc) {
		int a;
		String b;
		int i;
		
		// input 4개 
		for (i=1; i<N/2; i++) {
			a = sc.nextInt();
			b = sc.next();
			alpha[i] = b.charAt(0);
			a = sc.nextInt();
			tree[i][0] = a;
			a = sc.nextInt();
			tree[i][1] = a;
		}
		
		// input 개수가 변하는 지점 (N/2 || N/2+1)
		a = sc.nextInt();
		b = sc.next();
		alpha[i] = b.charAt(0);
		a = sc.nextInt();
		tree[i][0] = a;
		if (N%2==1) {
			a = sc.nextInt();
			tree[i][1] = a;
		}
		
		// input 2개 
		i++;
		for (; i<=N; i++) {
			a = sc.nextInt();
			b = sc.next();
			alpha[i] = b.charAt(0);
		}
	}
}

다음번에는..

input data의 개수가 가변적이라면 sc.nextLine() 으로 한 줄씩 읽어와서 처리하겠다 ~