[백준] 1920 자바

1920번: 수 찾기

백준의 실버4 문제입니다. 문제 내용은 배열 내에 특정 숫자가 존재하는지 안하는지 판단하는 아주 간단한 문제라 브론즈 문제라고 생각할 수 있지만 그렇지 않은 이유가 있었습니다.

 

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

public class Main {
    static int N, M;
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        
        M = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        
        //이중for문을 이용하여 하나하나 비교해보기
        for(int i=0; i<M; i++){
            int n = Integer.parseInt(st.nextToken());
            boolean check = false;
            for(int j=0; j<M; j++){
            	//존재하면 이번 숫자는 탐색 종료
                if(arr[j] == n){
                    check = true;
                    break;
                }
            }
            if(check){
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
        

    }
}

생각할 수 있는 가장 간단한 방법인 이중 for문으로 하나하나 대입하여 확인하는 방법입니다. arr를 모두 확인하며 숫자가 존재할 때에 check를 true로 변경하고 최종적으로 check가 true면 1 아니라면 0을 반환하는 방법입니다. 하지만, 이 방법은 시간 초과가 발생하게 됩니다.

시간초과

그래서 다른 방법으로 탐색을 진행해야 합니다. 그리고 이러한 데이터를 빠르게 탐색하기 방법으로는 이진탐색 (binary search )가 존재합니다. 자바의 Arrays 라이브러리에도 존재하는 라이브러리라 사용하기 좋습니다.

다만 이진탐색을 사용하기 위해서는 정렬된 데이터가 필요하기 때문에 미리 데이터를 정렬해줄 필요가 있습니다. 이진탐색을 이용해 완성한 코드입니다.

 

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

public class Main {
    static int N, M;
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        //이진탐색을 해주기 위한 데이터 정렬
        Arrays.sort(arr);
        
        M = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<M; i++){
            int n = Integer.parseInt(st.nextToken());
            //Arrays의 binarySearch를 사용합니다. 
            //arr 배열에서 숫자 n이 존재하는지 아닌지 판단합니다.
            //존재하지 않을 경우 음수를 반환합니다.
            if(Arrays.binarySearch(arr, n)>-1){
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
        

    }
}

이상입니다!