백준 - 수 찾기

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

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

[문제 설명]

크기가 N인 배열과 크기가 M인 배열이 주어질 때, N인 배열에서 M의 값이 있으면 1을 출력. 없으면 0을 출력하시오.

 

[접근 방법]

주어진 N배열이 정렬이 되지 않은 상태라서 선형검색을 통해 풀지, 이분탐색을 사용해서 풀지 고민을 한 문제다.

코드를 작성하기 전에 일단 시간복잡도를 먼저 계산하고 문제를 풀기로 마음 먹었다.

 

방법1) 선형 검색

선형검색의 경우, 단순이 M의 요소를 하나씩 정한 후 N의 모든 요소를 선형 검색하여 존재하면 1을 출력 존재하지 않으면 0을 출력하는 방법이다.

이렇게 될 경우 M개의 배열이 N개의 배열을 모두 돌아야하므로 시간복잡도는 O(NM)이 된다.

 

방법2) 이분 검색

이분검색의 경우 주의해야할 점은 검색해야할 배열이 정렬이 되어 있어야 한다는 점이다. 

이 문제는 배열이 정렬되지 않은 상태이므로 정렬을 위한 시간이 추가로 필요하게 된다. O(NlogN)

정렬한 후에는 이분 검색을 이용하는데 이분검색의 시간복잡도는 logN이고 M개의 요소들이 이분검색하므로

O(MlogN)이 됩니다.

따라서 총 시간복잡도는 정렬시간+배열M을 이분검색하는 시간 => NlogN+MlogN => (M+N)logN이 됩니다.

 

결론)

시간복잡도가 방법 1은 O(NM)이고 방법 2는 O((M+N)logN)이므로 2가 더 시간복잡도가 작습니다.

따라서 방법2를 사용하여 답을 구해보겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] providedArray = new int[N];
        String[] inputs = br.readLine().split(" ");
        for (int i = 0; i < N; i++) providedArray[i] = Integer.parseInt(inputs[i]);
        int M = Integer.parseInt(br.readLine());
        int[] targetArray = new int[M];
        inputs = br.readLine().split(" ");
        for (int i = 0; i < M; i++) targetArray[i] = Integer.parseInt(inputs[i]);
        // 방법1)선형 검사로 할시 시간복잡도는 O(NM) 공각복잡도는 O(N+M)
        // 방법2)N배열을 정렬하고 이분탐색으로 할 경우 시간복잡도는
        // 정렬에 NlogN + M*logN => (N+M)logN, 공간복잡도는 O(N+M)
        // -> 방법2 채택.
        // 주어진 배열 정렬
        Arrays.sort(providedArray);

        // 이분탐색
        for (int i = 0; i < M; i++) {
            int left = 0;
            int right = providedArray.length-1;
            boolean isExist = false;
            while (left <= right) {
                int mid = left + (right-left)/2;
                if (providedArray[mid] < targetArray[i]) left = mid+1;
                else if (targetArray[i] < providedArray[mid]) right = mid-1;
                else {
                    isExist = true;
                    break;
                }
            }

            if (isExist) System.out.println(1);
            else System.out.println(0);
        }
    }
}