[SWEA] 1231. 중위순회 (JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD

SW Expert Academy

[문제]

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

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

총 10개의 테스트 케이스가 주어진다.
총 노드의 개수는 100개를 넘어가지 않는다.
트리는 완전 이진 트리 형식으로 주어지며, 노드당 하나의 알파벳만 저장할 수 있다.
노드가 주어지는 순서는 아래 그림과 같은 숫자 번호대로 주어진다.

[풀이]

트리를 구현하는 방법은 3가지가 있는데, 이 문제는 트리가 완전 이진 트리 형식으로 주어지기 때문에 배열을 사용하여 구현하여도 메모리 낭비가 적다. 따라서 배열을 이용하여 구현하였다.

1. 노드개수+1 만큼의 tree 배열 생성

2. 각 정점 번호를 index로 하여 tree 배열에 알파벳을 저장한다.

3. in-order 형식으로 순회하며 답을 구한다.

package A0208;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class SWEA_중위순회 {
	
	static int N;
	static char[] tree;
	
	static void inOrder(int idx) { 
		if(idx>N) return;
		inOrder(2*idx); 
		System.out.print(tree[idx]);
		inOrder(2*idx+1);
	}
	
	public static void main(String[] args) throws Exception {
		
		//System.setIn(new FileInputStream("input_inorder.txt")); 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = 10;

		for(int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine()); //노드 개수
			tree = new char[N+1]; // 노드 개수+1만큼 트리배열 생성
			for(int i = 1; i <= N; i++) {
				StringTokenizer st =  new StringTokenizer(br.readLine());
				st.nextToken();
				tree[i] = st.nextToken().charAt(0);
			}

			System.out.print("#" + test_case + " ");
			inOrder(1);
			System.out.println();
		}

		
		}

}

[소감]

입력을 받아 트리로 만드는게 제일 어렵다.