백준 10815 숫자 카드[JAVA]

Ga0·2023년 5월 7일

baekjoon

목록 보기

43/137

문제 해석

문제는 간단하다 첫째 줄에는 상근이가 가지고 있는 숫자 카드의 수(N)을 입력하고, 둘째 줄에는 그 입력한 숫자 카드의 수(N)만큼 숫자카드를 입력받는다.
셋째 줄에는 상근이의 카드와 비교할 숫자 카드의 수 (M)을 입력받고, 네번째 줄부터는 (M)개 만큼 숫자카드를 입력받는다.
다 입력받았다면 비교할 숫자 카드의 수와 상근이가 가지고 있는 숫자 카드랑 비교를 해서, 상근의 카드 중에 비교할 숫자 카드가 존재하면 1을 출력하고, 없다면 0을 출력한다.
예를 들면, 6 3 2 10 -10 (상근이의 숫자 카드) 10 9 -5 2 3 4 5 -10 (비교할 카드의 수) 일때, 출력은 1 0 0 1 1 0 0 1 (상근에게 존재하는 카드일 경우 1로)이 나와야 한다.
여기까지는 문제를 이해하는데 어려움이 없지만, 여기서 포인트는 시간 이다.
그냥 같은 배열들의 요소를 비교하기 위해 for문을 쓴다면 O(n^2)시간이 소요될 것이다. for문이 2번이니까.
조사해본 결과, 보통 1초가 걸릴 때 입력의 최대 크기를 살펴보면 O(N)일 경우 1억, O(N^2)일 경우 약 1만, O(N^3)일 경우 약 500, O(2^N)일 경우 약 20, O(N!)일 경우 10이다.

//그냥 for문으로 풀면 1 <= N,M <= 500,000이므로
//최악의 경우 500000*500000 반복해야한다.
for(int i = 1; i <= 500000; i++){
	for(int j = 1; j <= 500000; j++){
    	if(MArr[i] == NArr[j]{
        	bw.write("1 "); //예를 들면 이런 식
        }
    }
}

위와 같은 예시로 시간 초과가 걸릴 것이다.
따라서, for문을 좀 더 효율적인 방식으로 사용해야하는데! 여기서 나온 개념이 이분/이진 탐색이다.
이진/이분 탐색의 시간 복잡도는 O(logN)으로 O(N)보다 상대적 빠른 알고리즘에 속한다.
즉, O(logN)은 O(N)보다 상대적 빠르므로 시간초과를 해결할 수 있을 것이다.

이분/이진 탐색이란?

위의 경우는 num이 middle보다 클 경우이다.
만약 작은 경우면, 아래와 같다.
이러한 과정을 코드로 풀어내면 이 문제는 다 푼 것이나 다름없다.

코드

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    static int N, M; //다른 함수에서도 쓰기 위해
    static int[] NArray; //다른 함수에서 상근이의 카드 요소를 체크해서 비교해야함
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine()); //상근이의 카드 개수

        NArray = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            NArray[i] = Integer.parseInt(st.nextToken()); //상근이의 카드
        }

        Arrays.sort(NArray); //상근이의 카드에 있는 요소를 체크해야하므로 정렬(이진탐색을 위해)

        M = Integer.parseInt(br.readLine()); //기준 카드 개수(비교)

        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < M; i++){
            //해당 비교 배열 요소들을 저장하지 않아도 됨 우리에게 필요한 것은 1과 0으로 된 문자열이니까.
            int num = Integer.parseInt(st.nextToken());

            bw.write(BinarySeach(num) + " ");
        }
        br.close();
        bw.flush();
        bw.close();
    }

    public static int BinarySeach(int num){ //이진/이분 탐색 => 요소를 하나씩 넣어서 비교한다.
        int left = 0; //인덱스 : 배열의 요소는 0부터 시작
        int right = N-1; //인덱스 : 배열의 요소는 0부터 시작하므로 N-1을 해준다.

        while(left <= right){ //left가 rigth보다 큰 경우는 이진 탐색 규칙에 어긋나므로 반복문 돌리지 X
            int middle = (left + right)/2; //중간 인덱스는 왼쪽 오른쪽의 더한 값에 나누기 2
            int middleValue = NArray[middle]; //중간 인덱스에 해당되는 값 => 이 값으로 비교한다.

            if(num > middleValue){ //만약 num이 중간값보다 크면
                left = middle +1;
            }else if(num < middleValue){ //만약 num이 중간값보다 작으면
                right = middle -1;
            }else return 1; //찾았을 경우 (middleValue == num)일 경우
        }
        return 0; //상근이의 카드에 num이 없을 경우
    }
}