일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- SWEA
- 1342
- 장고
- 2866
- 프로그래머스
- 17087
- solved.ac
- 20006
- 자바
- sloved.ac
- 파이썬
- programmers
- 알고리즘
- 23971
- 라이브러리
- 사용자정의필터
- 15965
- 25379
- 24511
- 11688
- PS
- java
- pccp
- PYTHON
- 6730
- 백준
- Django
- 9081
- Algorithm
- sovled.ac
Archives
- Today
- Total
코깽이의 코딩일기
Java 백준 9934 완전 이진 트리 본문
반응형
백준 링크
https://www.acmicpc.net/problem/9934
문제
입력
출력
입출력 예시
제출한 코드
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int n;
static int[] data;
static List<Integer>[] layer;
public static void main(String[] args) throws Exception {
init();
run();
}
private static void init() throws Exception {
n = Integer.parseInt(br.readLine());
// 각 level마다 노드를 저장할 List
layer = new List[n + 1];
for (int i = 1; i <= n; i++) {
layer[i] = new ArrayList<Integer>();
}
data = new int[(int) Math.pow(2, n) - 1];
int dataLen = (int) Math.pow(2, n) - 1;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < dataLen; i++) {
data[i] = Integer.parseInt(st.nextToken());
}
}
private static void run() {
// 로직 시작
recur(0, (int) Math.pow(2, n) - 1, 1);
// 정답 출력
for(int i = 1; i <= n ; i++) {
for(int output : layer[i]) {
System.out.print(output + " ");
}
System.out.println();
}
}
private static void recur(int start, int end, int depth) {
// 주어진 Level까지 진행
if (depth > n) {
return;
}
// 추가할 데이터
int now = (end + start) / 2;
// 해당 level에 추가
layer[depth].add(data[now]);
// 좌 우 퍼트리기
recur(start, now - 1, depth + 1);
recur(now + 1, end, depth + 1);
}
}
1. 완전이진트리가 무엇인지 다시 한번 확인한다.
2. 완전 이진트리는 2^n-1개 만큼 노드를 가지고 있고 좌우가 균형을 이루고 있는 모양이다.
3. 전체 범위에서 중앙에 위치하는 값이 해당 level에 속한 값이다.
4. 병합 정렬과 비슷한 방식으로 전체 데이터를 재귀를 이용해 타고 들어가면서 해당 level의 값을 찾아준다.
반응형
'PS > 백준' 카테고리의 다른 글
Java 백준 9081 단어 맞추기 (0) | 2024.05.02 |
---|---|
Java 백준 1027 고층 건물 (0) | 2024.04.29 |
Java 백준 10844 쉬운 계단 수 (0) | 2024.04.15 |
Java 백준 19538 루머 (0) | 2024.04.08 |
Java 백준 20006 랭킹전 대기열 (0) | 2024.04.03 |