[SWEA] #1231 - 중위순회

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

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

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

 

[제약 사항]

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

 

💡 아이디어

---

이 문제는 InOrder, PostOrder, PreOrder의 개념만 잘 알고 있다면 쉽게 풀 수 있다.

현재 문제에선 InOrder로 출력하라고 했으니 LVR이라고 생각할 수 있다.

그렇기 때문에 노드의 왼쪽으로 가는 코드가 첫 번째(L), 그다음에 부모 노드를 출력하는 코드가 두 번째(V),

마지막으로 노드의 오른쪽으로 가는 코드(R)를 마지막에 넣어주면 문제를 해결할 수 있다.

PostOrder의 경우 부모 노드가 가장 마지막에 나오기 때문에 LRV,

PreOrder의 경우 부모 노드가 가정 먼저 나오기 때문에 VLR이라는 것을 알 수 있고, 코드의 순서만 바꿔주면

원하는 데로 출력을 할 수 있다.

 

💡 소스코드

---

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class P_1231 {
 
    public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int TC = 1; TC <= 10; TC++) {
            int T = Integer.parseInt(br.readLine());
            char[] Tree = new char[T + 1];
 
            for (int i = 1; i <= T; i++) {
                StringTokenizer sz = new StringTokenizer(br.readLine());
                Tree[Integer.parseInt(sz.nextToken())] = sz.nextToken().charAt(0);
            }
 
            System.out.print("#" + TC + " ");
            PrintInOrder(Tree, 1);
            System.out.println("");
        }
 
        br.close();
    }
 
    public static void PrintInOrder(char[] Tree, int node) {
        if (Tree[node] != '0') {
            if (node * 2 < Tree.length)
                PrintInOrder(Tree, node * 2);
            System.out.print(Tree[node]);
            if (node * 2 + 1 < Tree.length)
                PrintInOrder(Tree, node * 2 + 1);
        }
    }
}

 

💡 결과

---