[백준 | 1920] 수 찾기 - Java

📃 제출 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

        String[] s1 = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(s1[i]);
        }

        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());
        String[] s2 = br.readLine().split(" ");
        for (int i = 0; i < M; i++) {
            bw.write(binarySearch(arr, Integer.parseInt(s2[i])) + "\n");
        }

        br.close();
        bw.flush();
        bw.close();

    }

    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return 1;
            }

            if (arr[mid] < target) {
                low = mid + 1;
            }

            if (arr[mid] > target) {
                high = mid - 1;
            }
        }
        return 0;
    }

}

✏ 풀이 과정

문제의 제한 사항과 시간 복잡도를 분석해보았다.

제한 시간 1초 
N(1 ≤ N ≤ 100,000)
M(1 ≤ M ≤ 100,000)
모든 정수의 범위는 -$2^31$ 보다 크거나 같고 $2^31$보다 작다.

• $n = 100,000$, 제한 시간은 1초로 컴퓨터가 1초에 1억번 연산한다 가정하고 계산을 해보았다.
  • $O(1)$의 시간 복잡도를 가지는 알고리즘은 항상 일정한 시간 연산 횟수를 수행한다
  • $O(log n)$ 의 시간 복잡도를 가지는 알고리즘은 최악의 경우 17번 이하의 연산을 수행한다.
  • $O(n)$ 의 시간 복잡도를 가지는 알고리즘은 최악의 경우 100,000번의 연산을 수행한다.
  • $O(n log n)$ 의 시간 복잡도를 가지는 알고리즘은 최악의 경우 1,660,000번의 연산을 수행한다.
  • $O(n^2)$의 시간 복잡도를 가지는 알고리즘은 최악의 경우 10,000,000,000 번의 연산을 수행한다.
• 제한 시간이 1초 이므로 $O(n^2)$의 이상의 시간 복잡도를 가지는 알고리즘 은 사용할 수 없다.

 

제출 코드 시간 복잡도

• for (int i = 0; i < N; i++) :
  • 이 루프는 0부터 N보다 작을 때까지 반복됩니다. 즉, N번 반복되므로 시간 복잡도는 O(N)이다.
• arrays.sort() :
  • Arrays.sort()는 배열을 정렬하는 메서드이다.
  • 최악의 경우: 퀵소트의 경우 피벗 선택이 나쁘거나 특정 상황에서는 $O(N^2)$ 의 시간 복잡도를 가질 수 있다.
  • 평균적인 경우: Dual-Pivot Quicksort의 평균적인 성능은 $O(N log N)$ 이다.
  • 따라서 Arrays.sort()의 시간 복잡도는 평균적인 경우 $O(N log N)$으로 표현하는 것이 일반적이며, 최악의 경우 $O(N^2)$ 로 표현할 수 있다.
• for (int i = 0; i < M; i++) :
  • 이 루프는 0부터 M보다 작을 때까지 반복된다. 즉, M번 반복되므로 시간 복잡도는 O(M)이다.
• binarySearch :
  • 이분 탐색을 구현한 메서드로, 매번 탐색 구간이 절반으로 줄어든다.
  • 따라서 시간 복잡도는 $O(log N)$ 입니다 (여기서 N은 배열의 크기).

 

전체적으로 코드의 시간 복잡도를 분석해보면

• 배열 입력 및 정렬:
  • 배열을 입력받고 정렬하는 데 걸리는 시간은 O(N log N)이다.
• 쿼리 처리:
  • 각 쿼리에 대해 이분 탐색을 수행하는데 걸리는 시간은 O(M log N)이다.

 

최종 시간 복잡도

전체적으로, 시간 복잡도는 두 부분의 합이다:

$O(N+M)log N)$