[D4] [S/W 문제해결 기본] 9일차 - 중위순회 - 1231
성능 요약
메모리: 19,112 KB, 시간: 125 ms, 코드길이: 1,065 Bytes
제출 일자
2024-01-04 00:54
접근 방법
1. 완전 이진 트리임으로 배열로 할 수 있다.
2. 이진 트리에서는 왼쪽 자식 노드는 현재 인덱스 * 2, 오른쪽 자식은 현재 인덱스 * 2 + 1이다.
3. 인덱스를 구한후 N보다 작다면 호출 한다. ( 중위 순회는 LVR(왼쪽가운데오른쪽 순서로 진행)
4. 순서대로만 구현하면 아주 쉬운 문제
풀이 코드
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
class Solution {
static String[] graph;
static StringBuilder sb = new StringBuilder();
static int n;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int tc = 1; tc <= 10; tc++) {
n = Integer.parseInt(br.readLine());
graph = new String[n+1];
for(int i = 1; i <= n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
graph[Integer.parseInt(st.nextToken())] = st.nextToken();
}
sb.append("#" + tc + " ");
// 중위순회
LVR(1);
sb.append("\n");
}
System.out.println(sb);
}
// V는 현재 노드를 뜻함
private static void LVR(int V){
// 왼쪽 먼저 구해준다.
int left = V * 2;
// 범위내에 있다면 왼쪽 호출
if(left <= n){
LVR(left);
}
// 가운데 노드의 key값을 저장한다.
sb.append(graph[V]);
// 오른쪽 인덱스를 구한뒤 범위내라면 호출한다.
if(left + 1 <= n){
LVR(left+1);
}
}
}
출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do
'알고리즘 - SWEA > D4' 카테고리의 다른 글
[SW expert Academy] SWEA 7829번 보물왕 태혁 자바(Java) (1) | 2024.01.05 |
---|---|
[SW expert Academy] SWEA 1233번 사칙연산 유효성 검사 자바(Java) (0) | 2024.01.04 |
[SW expert Academy] SWEA 1227번 미로2 자바(Java) (0) | 2024.01.02 |
[SW expert Academy] SWEA 1219번 길찾기 자바(Java) (0) | 2024.01.02 |
[SW expert Academy] SWEA 1218번 괄호 짝짓기 자바(Java) (0) | 2024.01.02 |