백준 5639 이진 검색 트리 Java

solved.ac = 실버 1

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

 

1. 접근

 

문제에 앞서 이진 탐색 트리에 대해 간략히 설명하자면 이진 탐색처럼 특정 값을 찾는데 빠른 속도와 특정 값의 삽입과 삭제에 강한 링크드 리스트의 장점을 합친 자료 구조이다.

 

구현 방법으로는 크게 두 가지로 나눌 수 있다.

1. 트리 Class를 만들어 현재 노드의 값과 다음 값을 비교하며 트리를 만든 후 재귀적으로 후위 출력하는 방법

2. Class를 별도 생성하지 않고 트리의 특성인 "나보다 작은값은 왼쪽에, 큰 값은 오른쪽에"를 이용하여 푸는 방법

 

나는 두 번째 방법을 이용해 별도의 Class 없이 문제를 풀어 보았다.

 

문제에 나와있는 이진 검색 트리의 조건을 통해 접근해보자!

즉, 왼쪽 서브트리와 오른쪽 서브 트리를 나누기 위해서는 현재 노드의 값보다 큰 값을 찾으면 된다!

예제를 앞선 방식으로 나누면 다음과 같다.

더 이상 나눌 수 없을 때까지 나눈 후 후위 탐색으로 출력해주면 끝!

 

2. 풀이

 

변수 세팅

static ArrayList<Integer> A;
public static void main(String[] args) throws IOException {
    A = new ArrayList<>();
    String str = "";
    // 별도의 종료지점이나 노드의 크기는 정해져 있지 않으니 주는대로 받자!
    while ((str = br.readLine()) != null) A.add(Integer.parseInt(str));
    solution();
}

 

DFS 호출 및 정답 출력

static void solution() {
    DFS(0, A.size() - 1);
    System.out.println(sb.toString());
}

 

DFS

static void DFS(int lt, int rt) {
    if (lt > rt) return;
    int mid = lt + 1;
    // 범위를 넘어가지 않는 선에서 중간점을 찾자!
    // 중간점 = 왼쪽 서브트리와 오른쪽 서브트리를 나눌 수 있는 기준점
    while (mid <= rt && A.get(mid) < A.get(lt)) mid++;

    // 왼쪽 서브트리
    DFS(lt + 1, mid - 1);
    // 오른쪽 서브트리
    DFS(mid, rt);
    sb.append(A.get(lt)).append('\n');
}

 

3. 전체코드