[백준] 1920 수 찾기 - 자바 JAVA

안녕하세요. 꼬맹입니다.

자바로 코딩테스트 준비하기 첫 문제로 백준 1920번 수 찾기를 풀어봤습니다.

---

[백준 1920번 수 찾기 문제]

 

문제 링크 : https://www.acmicpc.net/problem/1920

출처: https://www.acmicpc.net/problem/1920

 

M 집합의 수들이 A 집합에 포함되어 있는지 체크하여 있으면 1 없으면 0을 출력하는 문제였습니다.

---

[풀이]

 

우선 참고하기로 했던 알고리즘 강의 블로그에서 기초를 쌓기 위해 시간복잡도에 대해 공부헀습니다.

출처: https://blog.encrypted.gg/922?category=773649

컴퓨터는 1초에 약 3-5억번의 연산을 한다고 합니다.

문제를 단순하게 생각하면 A라는 수 집합에서 M 집합의 어떤 수가 포함되어 있는지 알기 위해 중첩 for문을 돌릴 수 있습니다.

하지만 시간 제한을 1초로 두고 있으며 주어진 자연수의 범위가 1부터 100,000만까지이기 때문에 중첩 for문을 돌린 다면 최악의 경우 100,000 X 100,000 = 1000억 번을 연산해야할 수 있습니다. 이는 3-5억번을 넘기 때문에 시간을 초과하게 됩니다.

 

따라서 A라는 수 집합에서 내가 원하는 수를 더 빠르게 탐색하기 위해 이분 탐색을 떠올렸습니다.

 

이분 탐색은

0 2 4 8 10 12 14 16 이라는 정렬된 수 집합이 있을 때 14를 찾고 싶다면

8(혹은 10)이라는 중간값을 기점으로 시작하여 14가 중간값보다 작은지 큰지를 체크해 탐색하는 기법입니다.

 

14는 8보다 크기 때문에 이제부터 8과 그 이전은 볼 필요가 없습니다.

최소값은 8 다음 수인 10, 최대값은 16, 중간값은 12가 됩니다.

10 12 14 16

 

다시 한 번, 14는 12보다 크기 때문에 12와 그 이전은 볼 필요가 없습니다.

최소값은 12 다음 수인 14 최대값은 16, 중간값은 14가 됩니다.

14 16

 

14는 중간값 14와 같아졌네요? 그럼 이분 탐색 종료입니다.

 

이진 탐색의 시간복잡도를 구해보겠습니다.

 

N개의 수 중에 1개를 찾는다고 하면 계속 그것의 절반을 나눈 수의 개수가 남게 됩니다.

N -> N/2 -> N/4 -> N/8 -> N/16 -> ... -> N/2^k

최악의 경우 N 열심히 절반씩 나뉘어져서 k번째에 1개만 남았을 때까지 탐색하게 되므로

N/2^k  = 1 일 때가 종료 조건이 됩니다.

그러면 N = 2^k -> log(2)N = k 가 됩니다.

 

따라서 이진 탐색의 시간 복잡도는 O(logN) (밑은 2) 입니다. 

N^2 보다 훨씬 빠르네요.

---

[풀이 정리 및 코드]

 

단순한 문제였기 때문에 금방 풀이가 정리됐습니다.

 

1. 입력 받기

2. A 집합에 대해 정렬하기

3. M 집합 수를 A 집합에서 이분탐색하기

4. 결과 출력하기

 

import java.util.Scanner;
import java.util.Arrays;

class Main {
    public static int binarySearch(int[] A, int N, int m){
        int min = 0;
        int max = N - 1;
        int mid = (min + max) / 2;
        while(min <= max){
            if (m > A[mid]){
                min = mid + 1;
                mid = (min + max) / 2;
            }
            else if (m < A[mid]){
                max = mid - 1;
                mid = (min + max) / 2;
            }
            else if (m == A[mid])
                return (1);
        }
        return (0);
    }
    public static void main(String[] args){
        //입력 받기
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i = 0; i < N; i++)
            A[i] = Integer.parseInt(sc.next());

        int M = sc.nextInt();
        int[] m = new int[M];
        for(int i = 0; i < M; i++)
            m[i] = Integer.parseInt(sc.next());

        //정렬하기
        Arrays.sort(A);

        //이분탐색하기
        //출력하기
        for(int i = 0; i < M; i++)
            System.out.println(binarySearch(A, N, m[i]));   
    }
}

---

연산 속도를 더 올리고 싶다면 Scanner 대신에 BufferReader를 쓰라고 하던데 아직은 Scanner 쓰는 법도 잘 모르겠어서 다음으로 미뤘습니다. 첫 문제는 쉬웠다!