[백준] 1920번 수 찾기(JAVA)

문제

- N개의 정수 A[1], A[2], ..., A[N]이 주어짐

- 이 안에 X라는 정수가 존재하는지 알아내는 것

- 모든 정수의 범위는 -2^31보다 크거나 같고 2^31보다 작음

 

고찰

처음에는 배열에 입력받은 것(input 배열)을 돌면서 입력받은 숫자가 있는지 돌아보도록 코드를 작성하였다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int inputNum = Integer.parseInt(br.readLine());		// 입력 받는 숫자 배열의 크기
        int[] input = new int[inputNum];			// 입력 배열

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        // 입력받은 숫자들 저장
        for(int i = 0; i<inputNum; i++){
            input[i] = Integer.parseInt(st.nextToken());
        }
		
        int check = Integer.parseInt(br.readLine());		// 체크하는 숫자 크기
        st = new StringTokenizer(br.readLine(), " ");
		
        // 입력받은 숫자가 있을 때까지
        while(st.hasMoreTokens()){
            int num = Integer.parseInt(st.nextToken());
            boolean result = false;
            // 입력 배열 내에 존재하는지 확인
            for(int i = 0; i<input.length; i++){
                if(input[i]==num){
                    result = true;
                    break;
                }
            }
            // 존재 여부에 따른 출력
            if (result == true) System.out.println("1");
            else System.out.println("0");
        }

        br.close();
    }
}

하지만, 이 코드는 주어진 테스트 케이스의 출력과는 동일하게 나오지만, 시간 초과가 나는 비효율적인 코드였다.

아직, 시간 복잡도도 계산하고 어떤 방식으로 코드를 짜야 효율적으로 코드를 작성하는 것인지 모르고 많이 부족한 것 같다.

통과한 코드는 이분탐색을 이용하여 보다 짧은 시간 내에 배열 내의 숫자를 탐색하여 입력받은 숫자의 존재 여부를 확인하는 코드로 작성하였다.

 

코드

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

public class Main {
    static int[] input;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int inputNum = Integer.parseInt(br.readLine());		// 입력 받는 숫자 배열의 크기
        int[] input = new int[inputNum];			// 입력 배열

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        // 입력받은 숫자들 저장
        for(int i = 0; i<inputNum; i++){
            input[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(input);    // 배열 정렬

        int check = Integer.parseInt(br.readLine());		// 체크하는 숫자 크기
        st = new StringTokenizer(br.readLine(), " ");
        
        // search 함수를 이용하여 배열 내 숫자 존재 여부 파악
        for(int i = 0; i<check; i++){
            if(search(Integer.parseInt(st.nextToken())) >= 0)
                System.out.println(1);
            else
                System.out.println(0);
        }

        br.close();
    }
    
    // 이분 탐색을 이용한 검색
    public static int search(int num){
        int left = 0;
        int right = input.length-1;

        while(left<=right){
            int mid = (left+right) / 2;    // 중간지점 계산
            
            // 중간 숫자보다 입력 숫자가 작을 때
            if(num < input[mid])
                // 오른쪽 기준점을 옮김
                right = mid - 1;

            // 중간 숫자보다 입력 숫자가 클 때
            else if(num > input[mid])
                // 왼쪽 기준점을 옮김
                left = mid + 1;
            
            // 중간 숫자와 입력 숫자가 같을 때
            else
                // 해당 숫자 return;
                return mid;
        }
        
        // 존재하지 않을 때
        return -1;
    }
}