[코딩테스트] 백준 1920번: 수 찾기 ( 이진 탐색 ) (JAVA)

시간 초과? 가 나와서 틀린 문제..

찾아보니 이진 탐색을 활용하여 풀어야 하는 문제라고 한다.

탐색 방법에 따른 시간복잡도를 알아야 풀 수 있는 문제더라..ㅠㅠ

정처기 공부하면서 다 외운애들인데 이런 문제에서 쓰이는구나..... 진심 자료구조의 세계 쉽지 않음..

 

애니웨이..

 

이진 탐색 트리(Binary Search Tree) ? 

 

🔽 이진 탐색 트리의 과정

1. 루트 노드의 키와 찾고자 하는 값을 비교. 찾고자 하는 값이라면 탐색 종료
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색 진행.
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색 진행.

일반적인 배열 순회 탐색 시간 복잡도는 O(N)

이진 탐색 알고리즘의 시간 복잡도는 O(log N)

 

이진 탐색 트리를 사용하기 위해서는 정렬 필수 !!

 

Arrays.sort(배열) 사용

 

이진 탐색 트리 Arrays.binarySearch() 사용

Arrays.binarySearch() 함수는 정렬된 배열에서 이진 탐색을 하는 함수이다.

Arrays.binarySearch(배열, int key) 형태로 배열에서 key 값을 이진 탐색으로 찾는다.

해당 key를 찾으면 그 위치를 리턴하고, 그렇지 않으면 -Insertion point -1 값을 리턴함 (음수를 리턴)

Insertion point 란?? key보다 큰 최초의 위치를 말함

ex) {1, 3, 4, 7, 9} 배열에서 6을 key로 찾으려 하는 경우 

insertion point 는 3이 되고 Arrays.binarySearch 함수를 써서 찾은 경우 -4가 리턴되는 것임 !

 

 

🔽 이용한 코드

import java.io.*;
import java.util.*;

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());
        
        // n개짜리 배열 생성
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // arr 배열 정렬
        Arrays.sort(arr);
        
        int m = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++){
            int num = Integer.parseInt(st.nextToken());
            
            // arr 배열에 num 숫자가 있는지 이진트리로 탐색
            // 있으면 찾은 위치(인덱스)가, 없으면 음수가 result에 저장됨
            int result = Arrays.binarySearch(arr, num);
            
            if(result < 0){
                System.out.println(0);
            }else{
                System.out.println(1);
            }
        }
    }
}

 

 

 

시간은 1288ms 나왔네요!!