[JAVA] 백준 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

---

로직은 단순하다..?? 하지만 범위가 너무 커서 시간초과가 나기 십상이기 때문에 단순 for문이 아니라 이분 탐색을 해야 한다!

 

---

문제풀이 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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());
        int[] narr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<n;i++){
            narr[i]=Integer.parseInt(st.nextToken());
        }

        int m =Integer.parseInt(br.readLine());
        int[] marr= new int[m];
        st= new StringTokenizer(br.readLine());

        for(int i=0;i<m;i++){
            marr[i]=Integer.parseInt(st.nextToken());
        }

        int[] check = new int[m];
        Arrays.fill(check,0);

        String str= "";
//--------------------입력처리-----------------------------------

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(marr[i]==narr[j]) check[i]=1;
            }
        }

        for(int i=0;i<check.length;i++){
            str+=check[i]+" ";
        }
        System.out.println(str);
    }
}

에라잇 역시나 시간 초과가 나버린다. 그리고 또 찾은 점은 String 객체끼리 더하는 방법은 메모리 할당과 해제를 발생시키는데, 덧셈 연산이 많아진다면 성능적으로 좋지 않다. 그래서 StringBuilder를 사용한다. 변경 가능한 문자열을 만들어 주기 때문에, String을 합치는 작업 시 좀 더 시간을 줄일 수 있다!! 

 

그래서 이분 탐색 방법으로 다시 시도!

 

간단하게 이분 탐색을 설명하자면

어떠한 요소 n을 찾으려고 할 때 모든 배열을 탐색하지 않고 배열의 중간값이 n보다 큰 지 작은 지 검사합니다.

만약 중간값이 n보다 작으면 중간값 이하는 무시하고

반대로 n보다 중간값이 크면 중간값 이상또한 무시합니다.

이런 방식으로 배열의 중간값과 n을 계속해서 비교해 나가는 것!!

 

 

 

이런 식으로 있고 없고를 탐색하는 것이다!

 

문제풀이 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_CT_10 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n =Integer.parseInt(br.readLine());
        int[] narr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder str = new StringBuilder();

        for(int i=0;i<n;i++){
            narr[i]=Integer.parseInt(st.nextToken());
        }

        Arrays.sort(narr); //정렬

        int m =Integer.parseInt(br.readLine());
        st= new StringTokenizer(br.readLine());

        for(int i=0;i<m;i++){
            int left = 0;
            int right=n-1;
            int num =Integer.parseInt(st.nextToken());

            while (left<=right){
                int midindex = (left+right)/2;
                int middle = narr[midindex];

                if (num==middle){ //찾으려는 수가 존재할때
                    str.append(1+" ");
                    break; //브레이크 걸어주기
                }

                if(num<middle) right=midindex-1; //right를 이동
                else if(num>middle) left=midindex+1; //left를 이동

                if(left>right){ //left가 right보다 커진다는건 찾는숫자가 존재하지 않는다는것
                    str.append(0+" ");
                    break;
                }
            }
        }
        System.out.println(str);
    }
}

헷 통과!!