글 읽기 - 시간초과 뜨는 이유좀 알고싶습니다(코드보고 조언 좀 주세요 ㅜㅜ)

komabomin 7년 전 0

시간초과 뜨는 이유를 모르겠습니다..... 코드 보고 조언이나 수정 좀 해주세요 ㅜㅜ

import java.util.Scanner;

public class Main {
	static int n;
	static int count = 0;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();

		int rootnum = scan.nextInt();
		TreeNode root = new TreeNode(rootnum);
		System.out.println("0");

		for (int i = 1; i < n; i++) {
			int num = scan.nextInt();
			TreeNode tree = new TreeNode(num);
			insert(tree, root);
			System.out.println(count);

		}
	}

	private static void insert(TreeNode node, TreeNode rootNode) {
		count++;
		int number = node.getData();
		if (number < rootNode.getData()) {
			if (rootNode.getLeft() == null) {
				rootNode.setLeft(node);
			} else {
				insert(node, rootNode.getLeft());
			}
		} else {
			if (rootNode.getRight() == null) {
				rootNode.setRight(node);
			} else {
				insert(node, rootNode.getRight());
			}
		}

	}

	static public class TreeNode {
		private int data;
		private TreeNode left;
		private TreeNode right;

		public TreeNode(int data) {
			this.data = data;
			this.left = null;
			this.right = null;
		}

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

		public TreeNode getLeft() {
			return left;
		}

		public void setLeft(TreeNode left) {
			this.left = left;
		}

		public TreeNode getRight() {
			return right;
		}

		public void setRight(TreeNode right) {
			this.right = right;
		}
		
		
	}
}

chogahui05 7년 전 1

이 문제 굉장히 어렵지요?? 물론 전 풀지 않았습니다.

간단하게 테스트 데이터 들어보겠습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 100000

이 경우에, 이진 탐색 트리에 추가하기 위해서 노드 탐색을 몇 번이나 할까요?

chogahui05 7년 전 1

제가 들어드린 데이터로 이진 탐색 트리를 구축하면

1 (root) - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - ...

이런 식으로 편향되게 구축이 되게 되는데요. 자료 구조 시간에도 많이 배우셨겠지만.

이게 이진 탐색 트리의 단점입니다.

트리 같은 경우, 탐색 시 시간 복잡도도 굉장히 중요한 요소 중 하나인데요.

저렇게 구축되면 O(n)이겠죠. 링크드 리스트보다 더 나쁩니다. (공간도 포인터 형 크기만큼이나 더 크고)

링크드 리스트는 head 포인터만 쭉 따라가면 되는데

이진 트리는 left, right 둘 다 비교해서 내려가야 하니까요. 복잡도는 같은데, 앞에 상수가 다르다고 할 수 있겠네요.

jre 8에서 부터는 HashMap이 레드 블랙 트리를 쓰게끔 만들어져 있는데요.

이전까지는 LinkedList를 사용했습니다. 같은 주소끼리 충돌이 났을 때.

이렇게 변한 게 무슨 큰 거냐고 생각하실지 모르겠지만요.

최악의 경우에 선형만큼 탐색해야 하는 것과

O(logn) 만큼 탐색하는 것과는 차이가 크겠지요?

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