글 읽기 - 반례좀 찾아주세요

(追記) (追記ここまで)

반례좀 찾아주세요

8944번 - 이진 검색 트리 2

itlockit 7년 전 0

반례좀 찾아주세요

예제 데이터 말고

새로운 데이터 셋

5 4 6 3 7 2 8 1 9 10 넣어봤는데 126이라고 나옵니다.

어디가 잘못되엇을까요?

package binarySearch_8944;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
class Tree {
	int number;
	int level;
	static int leftNodeCount[] = new int[20];
	static int rightNodeCount[] = new int[20];
	Tree leftNode;
	Tree rightNode;
	public void add(int number) {
		// 만약 입력 number가 트리의 number보다 크다면 오른쪽 노드로 넣어준다.
		if (this.number < number) {
			// 이때 노드가 비어있지 않다면 add함수를 호출하여 넣어준다.
			if (rightNode != null) {
				rightNode.add(number);
			} else {
				// 이때 노드가 비어있다면 rightNode를 만들어서 넣어준다.
				// 이때 자식의 레벨은 부모의 레벨 +1 이다.
				int childLevel = level + 1;
				rightNode = new Tree(number, childLevel);
			}
			// 만약 입력 number가 트리의 number보다 작다면 왼쪽 노드로 넣어준다.
		} else {
			if (leftNode != null) {
				leftNode.add(number);
			} else {
				// 이때 노트가 비어있다면 leftNode를 만들어서 넣어준다
				// 이때 자식의 레벨은 부모의 레벨 +1 이다.
				int childLevel = level + 1;
				leftNode = new Tree(number, childLevel);
			}
		}
	}
	// 왼쪽 서브트리의 레벨당 노드 개수 탐색
	public void leftSearch(Tree tree) {
		// 만약 트리가 비어있으면 탐색을 종료한다.
		if (tree == null) {
			return;
		}
		// 해당 레벨의 값을 증가시킨다.
		leftNodeCount[tree.level]++;
		// 왼쪽서브트리의 왼쪽트리와 오른쪽 트리를 탐색한다.
		leftSearch(tree.leftNode);
		leftSearch(tree.rightNode);
	}
	// 오른쪽 서브트리의 레벨당 노드 개수 탐색
	public void rightSearch(Tree tree) {
		// 만약 트리가 비어있으면 탐색을 종료한다.
		if (tree == null) {
			return;
		}
		// 해당 레벨에 값을 증가시킨다.
		rightNodeCount[tree.level]++;
		// 오른쪽 서브트리의 왼쪽트리와 오른쪽 트리를 탐색한다.
		rightSearch(tree.leftNode);
		rightSearch(tree.rightNode);
	}
	
	public void print2() {
		long leftNodeNumber = 0;
		long rightNodeNumber = 0;
		// 왼쪽 서브트리의 노드의 개수를 구한다.
		for(int i = 0; i<leftNodeCount.length;i++) {
			leftNodeNumber += leftNodeCount[i];
		}
		// 오른쪽 서브트리의 노드의 개수를 구한다.
		for(int i = 0; i<rightNodeCount.length;i++) {
			rightNodeNumber += rightNodeCount[i];
		}
		// 총 서브트리의 노드의 개수 , 오른쪽 서브트리의 노드의 개수를 조합을 한다.
		long result = combination(leftNodeNumber+rightNodeNumber,rightNodeNumber);
		// 왼쪽 서브트리의 레벨당 노드의 개수의 팩토리얼 만큼 경우의수가 생기므로 곱해준다.
		for(int i = 0; i<leftNodeCount.length;i++) {
			result *= factorial(leftNodeCount[i]);
		}
		// 오른쪽 서브트리의 레벨당 노드의 개수의 팩토리얼 만큼 경우의수가 생기므로 곱해준다.
		for(int i = 0; i<rightNodeCount.length;i++) {
			result *= factorial(rightNodeCount[i]);
		}
		System.out.println(result%9999991);
	}
	
	public long factorial(long n) {
		long temp = 1;
		if(n == 0)
			return 1;
		for(int i = 1; i <= n ;i++) {
			temp = temp * i;
		}
		return temp;
	}
	
	public long combination(long n, long k) {
		long p;
		long q;
		p = factorial(n);
		q = factorial(k);
		q = q * factorial(n-k);
		return p/q;
	}
	
	public Tree(int number, int level) {
		this.number = number;
		this.level = level;
	}
}
public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			StringTokenizer st = new StringTokenizer(br.readLine());
			// 테스트 갯수
			int T = Integer.parseInt(st.nextToken());
			for (int i = 0; i < T; i++) {
				st = new StringTokenizer(br.readLine());
				// 입력 개수
				int N = Integer.parseInt(st.nextToken());
				st = new StringTokenizer(br.readLine());
				Tree tree = new Tree(Integer.parseInt(st.nextToken()), 0);
				Tree.leftNodeCount = new int[20];
				Tree.rightNodeCount = new int[20];
				for (int j = 0; j < N - 1; j++) {
					tree.add(Integer.parseInt(st.nextToken()));
				}
				tree.leftSearch(tree.leftNode);
				tree.rightSearch(tree.rightNode);
				tree.print2();
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

반례좀 찾아주세요

itlockit 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말