[백준(Baekjoon)][자바(java)] 2957 : 이진 탐색 트리 / 트리를 사용한 집합과 맵

 

www.acmicpc.net/problem/2957

2957번: 이진 탐색 트리

 

문제 풀이

 

▶  문제에서 나온 그대로 이진 탐색 트리의 성질에 따라 TreeNode를 추가하는 addNode() 함수를 생성하고 함수 호출 시 마다 cnt++하는 방법   --> 시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static int cnt;
	
	static class TreeNode {
		private int d;				// data
		private TreeNode l, r;		// left, right
		public TreeNode( int d ) {
			this.d = d;
		}
		public void setL( TreeNode l ) {
			this.l = l;
		}
		public void setR( TreeNode r ) {
			this.r = r;
		}
		public void addNode( TreeNode c, int v ) {  // insert
			cnt++;
			TreeNode l = c.l, r = c.r;
			int d = c.d;
			if( d > v ) {
				if( l == null )	c.setL( new TreeNode( v ) );
				else			addNode( l, v );
			}
			else {
				if( r == null )	c.setR( new TreeNode( v ) );
				else			addNode( r, v );
			}
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n = Integer.parseInt( br.readLine() ), r, s, i;
		r = Integer.parseInt( br.readLine() );
		TreeNode root = new TreeNode( r );
		StringBuilder sb = new StringBuilder();
		sb.append( cnt + "\n" );
		for( i = 1; i < n; i++ ) {
			s = Integer.parseInt( br.readLine() );
			root.addNode( root, s );
			sb.append( cnt + "\n" );
		}
		br.close();
		
		System.out.println( sb.toString() );
		
	}
}

 

▶  TreeSet을 활용하는 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n = Integer.parseInt( br.readLine() ), num;
		
		int d[] = new int[n+2];	// depth
		d[0] = d[n+1] = -1;
		
		TreeSet<Integer> ts = new TreeSet<>();
		ts.add( 0 );
		ts.add( n+1 );
		
        long c = 0;
		StringBuilder sb = new StringBuilder();
		for( int i = 0; i < n; i++ ) {
			num = Integer.parseInt( br.readLine() );
			ts.add( num );
			d[num] = Math.max( d[ ts.lower( num ) ], d[ ts.higher( num ) ] ) + 1;
			c += d[num];
			sb.append( c + "\n" );
		}
		br.close();
		
		System.out.println( sb.toString() );
		
	}
}

 

ex)

8
3
5
1
6
8
7
2
4

order	num	dep	dep_sum ( c )
1	3	0	0
2	5	1	1
3	1	1	2
4	6	2	4
5	8	3	7
6	7	4	11
7	2	2	13
8	4	2	15

 

*  트리를 이용한 집합과 맵

-  노드가 총 n개이고, 각 노드의 번호는 [1, n] 
-  구해야 할 값 c는 노드를 추가한 순서에 따른 각 노드의 깊이의 누적 합
-  각 노드의 깊이/레벨( 루트 레벨 : 0 ) 값을 담을 int d[] 배열 생성 ( depth )
-  이진 탐색 트리에 추가한 노드의 번호를 담을 TreeSet 생성
-  이진 탐색 트리에 추가한 노드 num의 레벨을 구하는 법  =>  (num 보다 작은 번호들 중 가장 큰 번호) or (num 보다 큰 번호들 중 가장 작은 번호) 중 깊이가 더 큰 것을 구하고 + 1을 함 
-  lower_bound & upper_bound 값은 각각 TreeSet<E>의 lower(), higher() 메소드를 이용
-  맨 처음 루트에 대한 lower_bound, upper_bound를 구하기 위해서 d[]에서 d[0], d[n+1]을 -1로 초기화, TreeSet에도 0, n+1 값을 넣어줌.