알고리즘 문제/SWEA
[SWEA - Java] 1231. 중위순회
건복치
2021. 10. 24. 18:55
반응형
문제
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD
설명
트리를 구성할 때는 1차원 배열, 2차원 배열, 클래스 등 다양한 방법으로 구현할 수 있다.
[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현
이 문제는 1번 노드부터 완전 이진트리 형식으로 주어지기 때문에 1차원 배열만으로도 중위 순회를 처리할 수 있다.
따라서 배열의 각 인덱스에 해당하는 알파벳 값을 저장하고 재귀를 이용해 순회할 수 있다.
N번 노드의 왼쪽 자식 노드는 N * 2번 노드, 오른쪽 자식 노드는 N * 2 + 1번 노드가 된다.
중위 순회는 왼쪽 자식 노드 → 부모노드 → 오른쪽 자식 노드 순으로 트리를 순회한다.
따라서 N * 2 + 1번 → N번 → N * 2번 노드의 순으로 순회하면 된다.
전체 코드
import java.io.BufferedReadermport java.io.BufferedReaderㅑ;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Solution {
static char[] tree;
static int N;
static StringBuilder sb;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
int T = 10;
for(int test_case = 1; test_case <= T; test_case++) {
N = Integer.parseInt(br.readLine());
tree = new char[N+1];
for(int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
st.nextToken();
tree[i] = st.nextToken().charAt(0);
}
sb.append("#" + test_case + " ");
inOrder(1);
sb.append("\n");
}
System.out.println(sb.toString());
}
static void inOrder(int idx) { // 중위 순회
if(idx > N) return;
inOrder(2 * idx);
sb.append(tree[idx]);
inOrder(2 * idx + 1);
}
}
반응형