백준 10815번 숫자카드 <실버5> - 자바 java 이분탐색, HashSet

쉬워보이네요이

문제는 간단하다. 네번째 줄에 주어지는 숫자들이 두번째 줄에 주어진 숫자였다면 해당 위치에 1, 아니라면 0을 반환하면 되는 문제다.

 

다만 입력값 범위가 굉장히 크기에 시간복잡도 O(n) 관리가 필요하다.

 

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        // Input
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] N_arr = new int[N];
        for (int i = 0; i < N; i++) {  // 두번째줄 배열에 넣기
            N_arr[i] = sc.nextInt();
        }
        int M = sc.nextInt();
        int[] M_arr = new int[M];
        for (int i = 0; i < M; i++) {  // 네번째줄 배열에 넣기
            M_arr[i] = sc.nextInt();
        }
        int[] answer = new int[M];
 
        Arrays.sort(N_arr); // 이분 탐색을 위해 N 배열 정렬
 
        // Logic
        for (int i = 0; i < M_arr.length; i++) {
            answer[i] = BS(N_arr, M_arr[i]) ? 1 : 0; // 이분탐색 호출
        }
 
        for (int s : answer) {
            System.out.printf("%d ", s);
        }
 
        sc.close();
    }
 
    // Binary Search
    public static boolean BS(int[] arr, int n) {
        int left = 0;
        int right = arr.length - 1; 
        int mid;
 
        while (left <= right) { // left # # mid # # right 처럼 mid의 값으로
            mid = (left + right) / 2; 
            if (arr[mid] < n) {
                left = mid + 1;         // 중앙값이 찾는 값보다 작다면, 왼쪽 조여주기
            } else if (arr[mid] > n) {  // 크다면 오른쪽 조여주기.
                right = mid - 1;
            } else {                    // 같다면 true
                return true;
            }
        }
        return false;                    // 없다면 false
    }
}
 

 

초기에 이분탐색을 사용해서 작성한 코드이다,

이분탐색은 하나 하나 탐색하는 방법보다 성능이 좋으므로 해결될거라 생각했다.

 

헹 ㅋㅋ 어림없지

ㅋㅋㅎ 퇴근하고 더워서 녹은 몸으로 작성해서 틀려도 별 생각이 없었다.

문제를 한번 더 읽고 그냥 당연하게 HashSet으로 작성해버렸다.

 

import java.util.HashSet;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        // Input
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] N_arr = new int[N];
        HashSet<Integer> N_set = new HashSet<>();
        
        for (int i = 0; i < N; i++) {
            N_arr[i] = sc.nextInt();
            N_set.add(N_arr[i]);
        }
        
        int M = sc.nextInt();
        int[] M_arr = new int[M];
        for (int i = 0; i < M; i++) {
            M_arr[i] = sc.nextInt();
        }
        sc.close();
 
        // Logic
        for (int i = 0; i < M_arr.length; i++) {
            if (N_set.contains(M_arr[i])) {
                System.out.print("1 ");
            } else {
                System.out.print("0 ");
            }
        }
    }
}
 

간결하고, 배열을 정렬 할 필요도 없다. 단순히 값이 있는지만 해싱하기 때문에.

 

시간 복잡도를 비교해보면 

 

이진 검색 방식:

첫 번째 배열 정렬(N_arr): O(N log N)
두 번째 배열(M_arr)의 각 요소에 대한 이진 검색 수행: O(M log N)
총 시간 복잡도: O((N + M) log N)

이진 검색 방식은 N_arr sort가 필요했고, 정렬에는 O(N log N)이 필요했다.

M 요소에 대한 이진 탐색에는 O(M log N)이 필요하다. 따라서 전체 시간 복잡도는 O((N + M) log N)


해시셋 접근법:

첫 번째 배열에 대한 HashSet 빌드(N_arr): O(N)
두 번째 배열(M_arr)의 각 요소에 대한 조회 수행: O(M)
총 시간 복잡도: O(N + M)

 HashSet은 HashSet 생성에 O(N) 시간이 걸리고,  두 번째 배열의 각 요소에 대한 조회를 수행하는 데 O(M) 시간이 걸린다.

HashSet은 조회 작업에 대해 O(1) 평균 시간 복잡도를 제공하므로 전체 시간 복잡도는 O(N + M)이다.

 

아직도 자료구조가 많이 부족한거같다.. 실질적으로  쓰고있는거만 쓰고, 아직 어려운 문제를 많이 접하지 않아서 단순하게만 푸려는 경향이 있는 듯 싶다. 오히려 쉬운문제에 쓸때없이 많이 어렵게 생각할때도 있고

 

개념적으로 공부를 더 하고, 혼자서는 못 풀어도 골드 문제를 노려봐서 내가 생각하는 방향이랑 문제에서 제시하는 방향이랑 맞는지 비교하면서 부족함을 채워야겠다.