5639 : 이진 검색 트리 Java

2023. 11. 5. 17:45· Problem Solving/백준
목차
  1. 5639번: 이진 검색 트리

5639번: 이진 검색 트리

참고

[백준] 5639번: 이진 검색 트리 - JAVA

고쳐야 할 것

  • 코드를 너무 빨리 짜려는 습관
  • 일정 시간 이상 지나면 굳혀진 방향을 수정 고려하기

구현 고민

일단 반복문으로 방향을 잡고 시작했다.

  • 처음에는 current를 설정하고 current.data보다 작으면 current.left에 추가하고 current = current.left와 같이 현재 노드를 재설정해줬다.
  • 그리고 current.data 보다 클 경우 current = current.parent로 부모로 올라가 설정하려 했다.
    • 문제는 이렇게 위로 올라가려면 어디까지 올라가야 할지 설정하기가 어렵다는 점이다.
    • 현재 노드의 왼쪽 서브 트리는 노드의 키값보다 작다는 것을 가지고 설정해보려 했으나 이 경우 root 노드의 오른쪽 자식의 오른쪽 자식은 삽입할 수가 없게 됐다.
      • 오른쪽 서브 트리 자체가 현재 노드보다 큰 값이기 때문..
    • 아무튼 이 때 이 방식 포기했어야 했다..

그래서 중간에 재귀로 구현해보려 했는데 방식 자체는 똑같이 하려고 하니까 구현이 잘 안됐다..
어제부터 고민했는데 결국 혼자서 해결하기에는 너무 시간이 오래 걸릴 것 같아 포기하고 검색하기로 했다.

방식 자체는 root노드와 비교 후

  1. 루트 노드 보다 작은 경우
    1. 루트 노드의 왼쪽 자식이 빈 경우 채워주고
    2. 있는 경우 다시 왼쪽 서브 트리로 검색한다.
  2. 루트 노드 보다 큰 경우
    1. 오른쪽 자식이 빈 경우 채워주고
    2. 있는 경우 오른쪽 서브 트리로 검색한다.
public void insert(Node current, int data){
if(current.data > data){
if(current.left == null){
current.left = new Node(data, current);
} else {
insert(current.left, data);
}
} else{
if(current.right == null){
current.right = new Node(data, current);
} else {
insert(current.right, data);
}
}
}

역시 세상은 넓고 잘하는 사람은 쌔고 쌨다.

이 후에는 후위순회로 돌아주기만 하면 된다.

public static void postorder(Node current){
if(current == null) return;
postorder(current.left);
postorder(current.right);
// StringBuilder로 한 번에 모아서 출력
sb.append(current.data).append("\n");
}

전체 코드

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
public class Main {
static String input;
static StringBuilder ans = new StringBuilder();
public static void main(String[] args) throws IOException {
// input.txt에 테스트 케이스를 넣어놓으면 파일 끝에서 EOF를 반환하기 때문에 종료시킬 수 있다.
// System.setIn(Files.newInputStream(Paths.get("src/input.txt")));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Node root = new Node(Integer.parseInt(br.readLine()), null);
while ((input = br.readLine()) != null){
int data = Integer.parseInt(input);
root.insert(root, data);
}
postOrder(root);
System.out.println(ans);
br.close();
}
static void postOrder(Node current){
if(current == null) return;
postOrder(current.left);
postOrder(current.right);
ans.append(current.data).append("\n");
}
}
class Node{
int data;
Node parent;
Node left;
Node right;
public Node(int data, Node parent) {
this.data = data;
this.parent = parent;
}
public void insert(Node current, int data){
if(data < current.data){
if (current.left == null) {
current.left = new Node(data, current);
} else{
insert(current.left, data);
}
} else{
if(current.right == null){
current.right = new Node(data, current);
} else{
insert(current.right, data);
}
}
}
}

'Problem Solving > 백준' 카테고리의 다른 글

12865 : 평범한 배낭 - Java  (0) 2024.01.08
1106 : 호텔 Java  (0) 2024.01.07
30869 : 빨리기다리기 Java  (0) 2023.12.18
4179 불 Java  (0) 2023.10.30
  1. 5639번: 이진 검색 트리
'Problem Solving/백준' 카테고리의 다른 글
  • 12865 : 평범한 배낭 - Java
  • 1106 : 호텔 Java
  • 30869 : 빨리기다리기 Java
  • 4179 불 Java
greatwhite
greatwhite
greatwhite
우직하게
greatwhite
전체
오늘
어제
  • 분류 전체보기
    • Projects
      • 스위프] Woory
    • Python
    • Java
      • Spring
    • JPA
    • Problem Solving
      • 백준
      • 프로그래머스
    • Today I Learned

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 프로그래머스
  • MVC
  • 파이썬
  • math
  • backtracking
  • python
  • knapsack
  • 오블완
  • 그리디
  • 롬복
  • 백준
  • JPA
  • spring
  • dfs
  • BFS
  • erd 문법
  • dp
  • implementation
  • vi
  • 자바
  • sql
  • 티스토리챌린지
  • Mermaid
  • Euclidean
  • 다익스트라
  • Java
  • 스프링
  • @default
  • 비트마스킹
  • pigeonhole principle

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
greatwhite
5639 : 이진 검색 트리 Java
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.