[Algorithm Study] 백준 10815

14910 단어 algorithmalgorithm

문제 출처 : https://www.acmicpc.net/problem/10815

문제 접근

위의 문제는 이진탐색 알고리즘을 사용하는 문제로 둘째 줄에 주어진 카드 값을 정렬한 후에 상근이가 가지고 있는 카드에 대하여 이진탐색하며 상근이가 그 카드를 가지고 있는지를 판별하여 문제를 해결했습니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
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));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] N_arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N ; i++){
            N_arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(N_arr);
        int M = Integer.parseInt(br.readLine());
        int[] M_arr = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){
            M_arr[i] = Integer.parseInt(st.nextToken());
        }
        int[] answer = new int[M];
        for(int i = 0; i < M; i++){
            int s = 0, l = N-1;
            while(s < l){
                int mid = (s+l)/2;
                if(N_arr[mid] == M_arr[i]){
                    s = l = mid;
                    break;
                }
                if(N_arr[mid] > M_arr[i]){
                    l = mid;
                }
                if(N_arr[mid] < M_arr[i]){
                    s = mid + 1;
                }
            }
            if(N_arr[s] == M_arr[i]){
                answer[i] = 1;
            }
            else{
                answer[i] = 0;
            }
        }
        for(int i = 0; i < M; i++){
            System.out.print(answer[i]+" ");
        }
    }
}

좋은 웹페이지 즐겨찾기