[알고리즘풀이]백준 5639 : 이진 검색 트리 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 5639번 이진 검색 트리를 풀었습니다. 이를 정리해보고자 합니다.

5639번: 이진 검색 트리

 

본문

1) 문제

2) 과정

이번 문제는 5시간 생각을 해도 안풀리더라고요.. 그래서 몇몇 분들의 아이디어를 살펴보고 제가 이해해서 풀었던 문제입니다....

검색하면 시간도,, 뿌듯함도 반감..........

그래도 덕분에 제가 코드를 짤 때 나름대로의 고정관념이 있다는 걸 느낄 수 있었어요. 저는 꼭 배열에 입력받은 값을 넣은 뒤 배열을 이용해 트리를 완성시켜야한다고 생각했는데 루트 노드로부터 값을 입력받으며 아래로 넣어가는 방식은 생각을 못했거든요..! 그리고 제가 푼 방식은 아니지만 입력받은 숫자들을 바로바로 후위 순회한 결과로 바꾸시는 분도 계셨어요. 많이 신기하긴 했지만 아직 제 머리로는 생각해낼 방법이 아니라 생각해서 해당 방식으로 풀진 않았답니다. 이렇게 참고하면서 배워나가고 성장하는거죠..! (참고로 푸는데 도움을 줬던 블로그들은 아래 달아뒀습니다!)

 

돌아와서, 이번 코드의 방식은

1) 첫 값을 root노드로 설정한다.

2) 입력을 받으며 root노드에 값의 크기에 따라 자식을 추가하여 트리를 만든다.

3) postorder함수로 tree를 후위 순회하며 결과를 출력한다.

 

3)는 진짜 손쉽게 만들었지만,,, 2)가 너무 어려웠어요. 입력을 받는것도 IDE는 멈추지 않고 받아서 힘들었고, 트리를 만드는 것도 생각해내기 어려웠습니다. 이번 문제는 "트리만 만들면 장땡"인 문제였지만 그 과정이 꽤나 어려웠던 문제였습니다.

 

2-1) main

public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = "";
        Node rootNode = new Node(Integer.parseInt(br.readLine()));
        while((input = br.readLine())!=null){
            // TEST (테스트용 종료조건)
            // if(input.equals("")) break;
            rootNode.makeChild(Integer.parseInt(input));
        } 
        // TEST (잘들어갔는지 테스트)
        // Queue<Node> q = new LinkedList<>();
        // q.add(rootNode);
        // while(!q.isEmpty()){
        //     Node cur = q.poll();
        //     if(cur.left!=null) q.add(cur.left);
        //     if(cur.right!=null) q.add(cur.right);
       	/*Node의 toString에 return "["+left.val+","+val+","+right.val+"]";을 넣어 테스트했어요*/ 
        //     System.out.println(cur); 
        // }

        // Logic & Output
        postorder(rootNode);
    }

테스트용 코드를 짜는 것도 일이었던 이번 문제... 그래서 이번 포스팅에는 테스트용 코드들도 슬쩍 넣어봤어요. (오늘따라 남기고 싶어서 블로그에만 쓱 올려두고 깃헙엔 지웠습니다.) 테스트용 코드로 입력값이 빈 문자열이면 입력을 그만 받도록 제한을 거는 부분과 값이 잘 들어갔는지 테스트해보고 싶어서 BST방법으로 큐에 넣어 탐색하는 부분을 사용했었습니다. 

 

main자체로 할말이 있다면 이번에 새로 알게된 내용인 while의 괄호안에서 값을 할당하며 조건 체크하는 방법입니다. 저렇게 괄호로 할당부분을 감싸면 먼저 괄호 안의 내용을 실행하여 변수에 값을 할당하고, 이후 변수를 체크하여 while문을 돌게 했습니다! 이 방식은 꽤나 유익해서 후에도 자주 사용할 것 같아요. :)

 

2-2) postorder

    // Method - 좌-우-본
    private static void postorder(Node node){
    	// 좌우의 자식이 있다면 탐색해나가고(dfs방식) 없다면 좌->우->본 순서로 출력을 진행함.
        if(node.left != null) postorder(node.left);
        if(node.right != null) postorder(node.right);
        System.out.print(node);
    }

postorder는 좌측노드를 leaf로 갈 때까지 모두 실행하고 우측노드도 마찬가지로 실행한 뒤 자신을 출력하도록 했습니다. BOJ1991을 풀고 바로 풀었더니 꽤나 쉽게 생각났어요.

[알고리즘풀이]백준 1991 : 트리 순회 JAVA

 

2-3) Node

private static class Node{
        // Variable
        Node left,right;
        int val;
        
        // Constructor
        public Node(int val){
        	this.val = val;
        }
        
        // Method - insert child Node
        public void makeChild(int cNum){
            if(cNum<val){ //left child
            	// if null -> make cNum node to left/ if not null -> make cNum to left's child
                if(this.left!=null) this.left.makeChild(cNum);
                else this.left = new Node(cNum);
            }else{ // right child
            	// if null -> make cNum node to right/ if not null -> make cNum to left's child
                if(this.right!=null) this.right.makeChild(cNum);
                else this.right = new Node(cNum);
            }
        }
        // Method - for output
        public String toString(){return val+"\n";}
    }

Node클래스는 자신의 값과 좌측 자식 노드, 우측 자식 노드를 담기 위해 만들어졌습니다. toString은 Object클래스로부터 오버라이드한 함수로 자신의 값을 문제의 출력 형식에 맞게 리턴합니다. 

makechild는 "입력받은 값과 현재 노드의 크기", "직계자식의 유무"에 따라 행동을 수행합니다. 입력받은 값이 현재 노드의 값보다 작다면 왼쪽자식으로 두고, 크다면 오른쪽 자식으로 두도록 먼저 좌우를 나눠줍니다. 그리고 직계 자식이 없다면(this.left나 this.right가 null) 직계자식으로 만들고, 아니라면 직계 자식의 자식이 되도록 넘겨줍니다. 그렇게 값을 넘겨주다보면 처음에 받은 root로부터 자식들이 연결된 트리를 만드는 함수입니다!

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다. 깃헙엔 이런저런 주석도 마구 달아놨는데, 블로그엔 최소한의 주석만 달도록 정리했습니다. 세부적인 주석이 궁금하시다면 아래쪽에 링크된 깃헙 레포짓토리에 방문하여 확인해주세요!

import java.io.*;
import java.util.*;

public class Main{
	// Main
    public static void main(String[] args) throws IOException{
    	// Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = "";
        Node rootNode = new Node(Integer.parseInt(br.readLine()));
        while((input = br.readLine())!=null){
            rootNode.makeChild(Integer.parseInt(input));
        } 
        
        // Logic & Output
        postorder(rootNode);
    }
    
    // Method - 좌-우-본
    private static void postorder(Node node){
        if(node.left != null) postorder(node.left);
        if(node.right != null) postorder(node.right);
        System.out.print(node);
    }
    
    // Inner Class
    private static class Node{
        // Variable
        Node left,right;
        int val;
        
        // Constructor
        public Node(int val){
            this.val = val;
        }
        
        // Method - insert child Node
        public void makeChild(int cNum){
            if(cNum<val){ //left child
                if(this.left!=null) this.left.makeChild(cNum);
                else this.left = new Node(cNum);
            }else{ // right child
                if(this.right!=null) this.right.makeChild(cNum);
                else this.right = new Node(cNum);
            }
        }
        // Method - for output
        public String toString(){return val+"\n";}
    }
}

 

소요시간, 아이디어, 에러로그 등 더 자세히 이번 문제를 보고싶으시다면, 아래 깃헙 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/tree/BOJ5639.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비

 

가장 많은 도움이 되었던 블로그 : https://girawhale.tistory.com/59

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

입력받는 부분이 어려웠는데 while의 괄호 안에서 값을 할당하는 법을 알려준 블로그 : https://settembre.tistory.com/372

[백준/자바] 5639 이진 검색 트리

입력부분을 어떻게 하면 좋을까 고민하다가 발견한 블로그 : https://ukyonge.tistory.com/160

#백준_5639 이진 검색 트리 - Java 자바