2957 이진 탐색 트리 - 백준

이진 탐색 트리 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (하단 참고)

128 MB

6881

1113

790

24.976%

문제

이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수, 오른쪽 서브트리에는 X보다 큰 수만 저장되어 있어야 한다.

1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 입력으로 주어진다. 이 수열을 이용해서 이진 탐색 트리를 만들려고 한다. 이제 배열의 첫 번째 수를 루트 노드로 놓고, 다른 나머지 수들을 순서대로 삽입하면서 이진 탐색 트리를 만들려고 한다. 즉, 첫 번째 수를 제외한 모든 수에 대해서 insert(X,root)를 실행하는 것과 같다. 그 함수는 다음과 같다. 

이진 탐색 트리에 삽입하는 함수는 다음과 같다.

insert(number X, node N)
    카운터 C값을 1 증가시킨다
    if X가 노드 N에 있는 수보다 작다면
        if N의 왼쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 왼쪽 자식으로 만든다
        else
            insert(X, N의 왼쪽 자식)
    else (X가 노드 N에 있는 수보다 크다면)
        if N의 오른쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 오른쪽 자식으로 만들기
        else
            insert(X, N의 오른쪽 자식)

각 수를 삽입한 후에 C의 값을 출력하는 프로그램을 작성하시오. 카운터 C의 값은 0으로 초기화되어 있다.

입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 300,000)

다음 N개의 줄에는 수열의 수가 차례대로 주어진다. 수는 구간 [1, N]에 포함된 정수이고, 중복되지 않는다.

출력

N개의 줄에 각 수가 트리에 삽입된 후에 카운터 C값을 한 줄에 하나씩 출력한다.

예제 입력 1 복사

4
1
2
3
4

예제 출력 1 복사

0
1
3
6

예제 입력 2 복사

5
3
2
4
1
5

예제 출력 2 복사

0
1
2
4
6

예제 입력 3 복사

8
3
5
1
6
8
7
2
4

예제 출력 3 복사

0
1
2
4
7
11
13
15

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #3 5번

• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: Green55
• 문제의 오타를 찾은 사람: jh05013
• 어색한 표현을 찾은 사람: jyc4836

시간 제한

• Java 8: 5 초
• Java 8 (OpenJDK): 5 초
• Java 11: 5 초
• Kotlin (JVM): 5 초

풀이

첫째 줄 들어오는 input 갯수

다음 줄부터 n개까지 input 갯수

 

출력은 카운터의 값을 출력

즉 현재 각 노드 입력시마다의 높이를 더해서 누적값을 표기해주면 된다.

 

예를 들어 예제2에서

5와 3이 입력된 상태에서 2를 추가하게 되면

5의 높이는  3의 높이는 1이 되고 2의 높이는 3의 높이(바로 직전에 있는 number)에 +1을 한 값이다.

 

이는 x의 높이 = x의 값보다 작은 것들 중 가장 큰 것의 높이와 x의 값보다 큰 것들중 가장 작은 것의 높이를 비교한 후 거기에 +1 한 것 (max(depth[treeset.lower(number)], treeset.higher(number)) + 1

 

여기서 카운터는 누적합이니까 누적합 출력하면 해결된다.

 

코드

package test2957;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
	static int N;
	static long counter = 0;
	static int depth[];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);
		
		N = sc.nextInt();
		depth = new int[N+2];
		
		// 초기화
        TreeSet<Integer> treeSet = new TreeSet<>();
        // 경계값을 추가한다. treeSet을 이용하기 위해서는 경계값이 필수이다.
        treeSet.add(0);
        treeSet.add(N+1);

        // 경계값의 depth는 -1로 입력
        depth[0] = -1;
        depth[N+1] = -1;

        for(int i=0; i<N; i++) {
            int number = sc.nextInt();
            // lower와 highter를 비교해서 더 depth가 큰 것에 +1을 한게 현재 숫자의 depth
            depth[number] = Math.max(depth[treeSet.lower(number)], depth[treeSet.higher(number)]) + 1;
            treeSet.add(number);

            // count 정보 update
            counter += depth[number];
            sc.write(counter + "\n");
        }
		
		sc.close();

	}
	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void write(String sb) throws IOException {
			writer.write(sb);
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}