[SWEA] 1231. [S/W 문제해결 기본] 9일차 - 중위순회

문제

다음은 특정 단어(또는 문장)를 트리 형태로 구성한 것으로, in-order 형식으로 순회하여 각 노드를 읽으면 원래 단어를 알 수 있다고 한다.

 
위 트리를 in-order 형식으로 순회할 경우 SOFTWARE 라는 단어를 읽을 수 있다.

[제약 사항]

총 10개의 테스트 케이스가 주어진다.

총 노드의 개수는 100개를 넘어가지 않는다.

트리는 완전 이진 트리 형식으로 주어지며, 노드당 하나의 알파벳만 저장할 수 있다.

노드가 주어지는 순서는 아래 그림과 같은 숫자 번호대로 주어진다.
 

 

 

풀이방법

중위 순회 방식은 왼쪽의 자식노드 -> 부모노드 -> 오른쪽 자식노드 순으로 방문하는 알고리즘이다.

 

입력이 너비를 기준으로 1, 2, 3, 4,...로 입력되었기 때문에

 

노드에 자식노드를 가르키는 포인터 정보 없이 배열로 받아 인덱스와 재귀로만 해결할 수 있다.

 

n노드가 가르키는 왼쪽 자식노드는 n * 2이고, 오른쪽 자식노드는 n*2 + 1이 된다.

 

따라서 n*2 노드 -> n노드 -> n*2+1노드 순으로 방문하면 된다.

 

소스코드

package samsung;

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

public class s_1231 {
	static char[] a;
	static int n;
	public static void inOrder(int idx) {
		if(idx > n) return; 
		inOrder(2 * idx);
		System.out.print(a[idx]);
		inOrder(2 * idx + 1);
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for(int t = 1; t <= 10; t++) {
			n = Integer.parseInt(br.readLine());
			a = new char[n + 1];
			for(int i = 1; i <= n; i++) {
				StringTokenizer tk = new StringTokenizer(br.readLine());
				tk.nextToken();
				a[i] = tk.nextToken().charAt(0);
			}
			System.out.print("#" + t + " ");
			inOrder(1);
			System.out.println();
		}
	}
}