[BOJ 9489] 사촌 (Java, 트리)알고리즘/트리2023. 6. 26. 20:40
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/9489
문제 풀이
- (중요) 두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라 함
- 입력 초기화할 때 이전 노드와 현 노드 차이가 1이 아닌 경우 부모 노드 인덱스(parentIdx)를 변경하여 PARENT 배열 정의
- PARENT 배열을 구한 후 선형 탐색 하여 O(N) 시간복잡도 가짐
TARGET 노드가 있을 때
TARGET 노드의 부모와 비교 대상 노드의 부모가 다르지만, 두 부모의 부모가 같다면 둘은 형제 노드라 할 수 있다
- 첫번째 정수가 트리의 루트 노드
- 다음에 등장하는 연속된 수의 집합은 루트의 자식을 나타냄, 이 집합에 포함된 수의 첫번째 수는 항상 루트 노드 + 1보다 크다
- 그 다음부터는 모든 연속된 수의 집합은 아직 자식이 없는 노드의 자식이 된다.
- 집합은 수가 연속하지 않는 곳에서 구분된다 ( => 이전 노드와 현 노드의 값의 차이가 1이 아니면 부모 노드 인덱스(parentIdx) 증가)
실수*
입력 정보 초기화시
Loop 바깥에서 Root 노드를 부모 노드 정보를 직접 초기화 할 경우 ArrayIndexOutOfBound 에러 발생
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, K, TARGET_IDX;
static int[] DATA, PARENT;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
String input = "";
while(true) {
input = br.readLine();
if("0 0".equals(input)) break;
st = new StringTokenizer(input);
N = Integer.parseInt(st.nextToken()); // 노드의 수
K = Integer.parseInt(st.nextToken()); // 사촌의 수
st = new StringTokenizer(br.readLine());
DATA = new int[N + 1];
PARENT = new int[N + 1];
PARENT[0] = -1;
int parentIdx = 0;
for(int i = 1; i <= N; i++) {
DATA[i] = Integer.parseInt(st.nextToken());
if(DATA[i] == K) TARGET_IDX = i;
if(i > 1 && DATA[i] - DATA[i - 1] != 1) parentIdx += 1;
PARENT[i] = parentIdx;
}
pro();
}
}
static void pro() {
int cnt = 0;
for(int i = 1; i <= N; i++) { // 부모 노드가 같지 않고, 부모 노드가 형제인 경우
if(PARENT[i] != PARENT[TARGET_IDX] && PARENT[PARENT[i]] == PARENT[PARENT[TARGET_IDX]]) cnt += 1;
}
sb.append(cnt).append("\n");
}
public static void main(String[] args) throws Exception {
input();
System.out.println(sb);
}
}
반응형
'알고리즘 > 트리' 카테고리의 다른 글
[BOJ 14267] 회사 문화1 (Java, DFS, Tree) (0) | 2023.06.26 |
---|---|
[BOJ 1068] 트리 (Java, DFS) (0) | 2023.06.26 |
[BOJ 3584] 가장 가까운 공통 조상 (Java, DFS, LCA) (0) | 2023.06.26 |
[BOJ 20364] 부동산 다툼 (Java, Tree) (0) | 2023.06.26 |
[BOJ 15900] 나무 탈출 (Java, DFS, Tree) (0) | 2023.06.26 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!