BOJ - 1920

1. 문제

https://www.acmicpc.net/problem/1920

2 .풀이

처음에 그냥 for문을 돌렸는데 시간초과가 발생하여 기준 배열을 정렬 후 이분탐색을 이용하여 구간을 나누고 문제를 풀었다.

import java.util.*;
import java.io.*;
public class Main1920 {
    static int N, M;
    static int [] nArr;
    static int [] mArr;
    static int largeN;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nArr = new int [N];
        largeN = 0;
        for(int i = 0; i < N; i++){
            int num = sc.nextInt();
            nArr[i] = num;
            largeN = Math.max(largeN, num);
        }
        Arrays.sort(nArr);
        M = sc.nextInt();
        mArr = new int[M];
        StringBuilder sb =  new StringBuilder();
        for(int i = 0; i < M; i++){
            mArr[i] = sc.nextInt();
        }
        for(int i = 0; i < M; i++){
            if(mArr[i] < nArr[(N-1)/2]){
                boolean flag = false;
                for(int j = 0; j < (N-1)/2; j++){
                    if(mArr[i] == nArr[j]) {
                        flag = true;
                        break;
                    }
                }
                if(flag)
                    sb.append("1").append("\n");
                else
                    sb.append("0").append("\n");
            }
            else if(mArr[i] == nArr[(N-1)/2]){
                sb.append("1").append("\n");
            }
            else {
                boolean flag = false;
                for(int j = (N-1)/2+1; j < N; j++){
                    if(mArr[i] == nArr[j]) {
                        flag = true;
                        break;
                    }
                }
                if(flag)
                    sb.append("1").append("\n");
                else
                    sb.append("0").append("\n");
            }

        }
        sb.delete(sb.length()-1, sb.length());
        System.out.print(sb.toString());

    }

}

3. 적용된 알고리즘

정렬, 이분탐색