BOJ : 10815

1. 문제

 

2. 문제 설명 및 알고리즘 설계

주어진 카드들과 상근이가 가지고 있는 카드를 이용해서 주어진 카드 중 상근이가 가진 카드를 추출하는 문제이다.

이분탐색 알고리즘을 사용하여야 한다고 생각했지만 시간초과가 나지 않을 것이라는 안일한 생각으로 다르게 짰다가 틀렸다.

 

3. 코드

package week9;

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

public class Q10815_boj {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        int N = Integer.parseInt(br.readLine());
        int card[] = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            card[i] = Integer.parseInt(st.nextToken());
        }

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

        int result[] = new int[M];

        Arrays.sort(card);
        for(int i=0;i<M;i++){
            int low = 0, high = card.length-1;
            while ( low <= high ){
                int mid = (low+high)/2;
                if(card[mid] == sang[i]){
                    result[i] = 1;
                    break;
                }else if( card[mid] < sang[i]){
                    low = mid+1;
                }else{
                    high = mid-1;
                }
            }
        }

        for(int i=0;i<M;i++){
            System.out.print(result[i]+" ");
        }
    }
}

 

4. 시간복잡도

O(N)

O(logN)

 

5. 결과