[백준, 10815번] 숫자 카드 (정렬, 이진 탐색, Java)

 

문제설명

입력 & 출력

나의 풀이

잘못된 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer token = new StringTokenizer(br.readLine());
        int[] arrN = new int[N];

        for (int i = 0; i < N; i++) {
            arrN[i] = Integer.parseInt(token.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        int[] arrM = new int[M];

        token = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            arrM[i] = Integer.parseInt(token.nextToken());
        }

        int[] result = new int[M];

        for (int i = 0; i < N; i++) {
            if(isExist(arrM,arrN[i])){
                for (int j = 0; j < M; j++) {
                    if(arrM[j] == arrN[i]){
                        result[j]++;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(result));

    }

    private static boolean isExist(int[] arr, int n){
        return Arrays.stream(arr).anyMatch(el -> el == n);
    }
}

 

이번 숫자 카드문제는 선형 탐색을 한다면 N = 100,000, M = 100,000일 때, 약 10억 번의 연산이 필요합니다. 이는 시간 초과를 유발할 가능성이 높습니다.

 

이진 탐색 알고리즘 사용 코드

이진 탐색을 사용한다면 arrM을 정렬 후 탐색하므로, 정렬 시간 O(M log M) + 이진 탐색 시간 O(N log M) 예를 들어, N = 100,000, M = 100,000일 때, 약 200만 번의 연산으로 해결 가능합니다.

 

 

 

main 문

1. 배열 정렬
   • arrN 배열은 이진 탐색을 사용하기 전에 정렬되어야 하므로 Arrays.sort(arrN)을 사용하여 배열을 오름차순으로 정렬합니다.
2. 이진 탐색을 통해 배열 arrM의 요소가 arrN에 있는지 확인
   • arrM 배열의 각 요소에 대해 binarySearch 함수를 호출하여, 해당 값이 arrN에 존재하는지 확인합니다.
   • 존재하면 1을, 존재하지 않으면 0을 결과 문자열에 추가합니다.
3. 결과 출력
   • StringBuilder를 사용하여 결과를 문자열로 이어붙이고, 마지막에 한 번에 출력합니다.

binarySearch 함수

 

• left와 right 포인터를 사용하여 배열의 중앙을 찾아가며 탐색을 진행합니다.
• 값이 발견되면 true를 반환하고, 값을 찾지 못하면 false를 반환합니다.

 

이진 탐색에 대한 자세한 내용은 아래의 포스팅에서 확인 가능합니다.

[Algorithm] 이진 탐색 알고리즘 : 데이터 정렬과 검색 최적화 (Binary Search, Java)