[BOJ] 백준 10815번 : 숫자 카드 (JAVA)

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

10815번: 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

 

풀이

전형적인 이분탐색 문제였습니다. M개의 확인에 대해서 N개의 카드를 전부 확인하는 선형탐색을 사용하면 시간복잡도가 ON(MN)으로 시간초과를 막을 수 없습니다. 따라서 시간복잡도가 O(logN)인 이분탐색을 사용해서 O(MlogN)만큼 줄여야 통과를 할 수 있습니다.

그리고 이분탐색할 배열은 반드시 정렬이 되어야 한다는 점을 꼭 명심하시길 바랍니다.

이분탐색을 모르시는 분을 위해 간략하게 말씀드리자면, 어떠한 요소 N을 찾으려고 할 때 모든 배열을 보지 않고, 배열의 중간값이 N보다 큰 지 작은 지 검사합니다. 만약 중간값이 N보다 작으면 중간값 이하는 모두 볼 필요가 없습니다.

반대로, N보다 중간값이 크면 중간값 이상은 볼 필요가 없어집니다. 이와 같은 방식으로 배열의 중간값과 N을 계속해서 비교해 나가는 것이 핵심입니다.

가령, 배열 A = {1, 2, 3, 4, 5} 가 주어져 있고, 찾으려는 수가 4라고 가정해 봅시다.

0과 4의 중간 인덱스는 2이므로 중간값은 3이 됩니다. 3은 4보다 작기때문에 1, 2, 3은 볼 필요가 없어집니다. 따라서 우리는 탐색할 배열은 {4, 5}로 좁혀집니다.

0과 1의 중간 인덱스는 0이므로 중간값은 4가 됩니다. 우리가 찾으려는 수는 4이기때문에 배열의 4가 있다고 판단 내릴 수 있습니다.

아래는 위의 과정을 소스 코드로 옮긴 것입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine()); // 카드의 개수
        int[] cards = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(cards); // 이분탐색할 배열은 정렬되어 있어야 함.
        int M = Integer.parseInt(br.readLine()); // 구별할 수의 개수
 
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int temp = Integer.parseInt(st.nextToken());
            sb.append(binarySearch(cards, N, temp) + " ");
        }
 
        bw.write(sb.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static int binarySearch(int[] cards, int N, int search) {
        int first = 0;
        int last = N - 1;
        int mid = 0;
 
        while (first <= last) {
            mid = (first + last) / 2; // 중간 인덱스
 
            if (cards[mid] == search) { // 중간값과 찾으려는 수가 같은 경우
                return 1;
            }
 
            if (cards[mid] < search) { // 중간값이 찾으려는 수보다 작으면, 그 이하로는 볼 필요 없음.
                first = mid + 1;
            } else { // 중간값이 찾으려는 수보다 크면, 그 이상으로는 볼 필요 없음.
                last = mid - 1;
            }
        }
 
        return 0;
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.