티스토리 뷰
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
import java.io.*;
import java.util.StringTokenizer;
public class boj_2250 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int n;
static int order = 0;
static int[] cnt, left, right;
static Node[] a;
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
a = new Node[n+1];
cnt = new int[n+1];
left = new int[n+1];
right = new int[n+1];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
a[x] = new Node(y, z);
if (y != -1) cnt[y] += 1;
if (z != -1) cnt[z] += 1;
}
// left, right 추가하면서 cnt에 부모가 존재하는지 체크
// cnt에서 값이 0 이라면 부모가없고 루트로 볼 수 있다.
int root = 0;
for (int i = 1; i <= n; i++) {
if (cnt[i] == 0) {
root = i;
}
}
// 열의 순서는 inoroder한 순서와 같다.
inorder(root, 1);
// 최대 depth와 해당 depth 에서의 최소 order, 최대 order
int maxdepth = 0;
for (int i = 1; i <= n; i++) {
int depth = a[i].depth;
int order = a[i].order;
if (left[depth] == 0) {
left[depth] = order;
} else {
left[depth] = Math.min(left[depth], order);
}
right[depth] = Math.max(right[depth], order);
maxdepth = Math.max(maxdepth, depth);
}
// ans
int ans = 0;
int ans_level = 0;
for (int i = 1; i <= maxdepth ; i++) {
if (ans < right[i] - left[i] + 1) {
ans = right[i] - left[i] + 1;
ans_level = i;
}
}
System.out.println(ans_level + " " + ans);
}
static void inorder(int node, int depth) {
if (node == -1) return;
inorder(a[node].left, depth + 1);
a[node].order = ++order;
a[node].depth = depth;
inorder(a[node].right, depth + 1);
}
}
class Node {
int left;
int right;
int order;
int depth;
public Node(int left, int right) {
this.left = left;
this.right = right;
}
}
|
cs |
- 트리
- inorder 활용해서 열 번호 구하는것도 생각 못했고 구현하기도 어렵다.
반응형
'PS > boj' 카테고리의 다른 글
BOJ)1389 - 케빈 베이커의 6단계 법칙 (0) | 2022.09.24 |
---|---|
BOJ)15686 - 치킨배달 (0) | 2022.09.22 |
boj)1991 - 트리 순회 (0) | 2020.12.11 |
boj)7562 - 나이트의 이동 (0) | 2020.12.10 |
boj)11723 - 집합 (0) | 2020.12.09 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- dreamcoding
- 드림코딩
- 패스트캠퍼스 컴퓨터공학 완주반
- http
- Spring Security
- GCP
- js api
- 이펙티브자바 아이템60
- BOJ
- js promise
- java
- REST API
- JS 딥다이브
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 이펙티브자바
- 모던자바스크립트
- 프로그래머스
- 이펙티브자바 아이템59
- HTTP 완벽가이드
- js array
- 이펙티브자바 스터디
- 김영한 http
- 집 구하기
- HTTP 완벽 가이드
- 백준
- 김영한 JPA
- 프로그래머스 SQL
- 백기선 스터디
- 킹수빈닷컴
- JPA 연관관계 매핑
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
글 보관함