글 읽기 - 이진 탐색 트리 시간초과

mygumi 7년 전 0

이진트리를 만들 때 아래 소스가 정석 아닌가요...?

어떻게 풀어야하는거죠?

삽입하면서 카운트를 세면 안되는건가요

import java.util.Scanner;
 
public class Main {
	public static int count = 0;
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main m = new Main();
        Main.BST tree = m.new BST();
        
        int n = sc.nextInt();
        
        for(int i=0;i<n;i++) {
        	tree.put(sc.nextInt());
        	System.out.println(count);
        }

    }   
    class BST
    {
        private BSTNode root;

        public void put( int key )
        {
            if ( root == null )
            {
                root = new BSTNode( key );
            }
            else
            {
                root.put( key );
            }
        }

        public Object get( int key )
        {
            return root == null ? null : root.get( key );
        }
        
    }

    class BSTNode
    {
        private int key;
        private BSTNode left, right;

        public BSTNode( int key )
        {
            this.key = key;
        }

        public void put( int key )
        {
        	++count;
            if ( key < this.key )        
            {             
                if ( left != null )             
                {   
                    left.put( key );             
                }             
                else             
                {                 
                    left = new BSTNode( key );      
                }         
            }         
            else if ( key > this.key )
            {
                if ( right != null )
                {
                    right.put( key );
                }
                else
                {
                    right = new BSTNode( key );
                }
            }
            else
            {
                this.key = key;
            }
        }

        public Object get( int key )
        {
            if ( key == this.key )
            {
                return key;
            }

            if ( key < this.key )
            {
                return left == null ? null : left.get( key );
            }
            else
            {
                return right == null ? null : right.get( key );
            }
        }
    }
}

flflds0811 7년 전 1

이진탐색트리의 삽입,삭제,탐색 시간복잡도는 O(h)입니다.

O(logn)<=O(h)<=O(n)이므로 O(n)으로 볼 수 있습니다.

하나의 입력마다 삽입을하며 카운트를 한다면, 알고리즘의 시간복잡도는

최악의 경우 O(1)+O(2)+...O(n) = O(n^2)

n이 30만까지 들어온다고 하였으므로 30만 제곱의 시간이 걸리게 되므로

제한시간 1초에는 불가능합니다.

이진탐색트리에서 삽입되는 특징을 찾아서 O(n^2)보다 빠른 시간복잡도의

알고리즘으로 문제를 해결해야합니다.

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

문제

문제

출처

ICPC

이진 탐색 트리 시간초과

mygumi 7년 전 0

flflds0811 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말