백준 1920 자바

풀기 전

자연수 N 과 M 이 각각 10만개 씩 들어갈 수 있어서 각각의 정수가 들어가 있는지 단순히 판단하려면 특정 배열의 원소 기준으로 다른 배열에 속하는지(A) 에 판단하는 것이다. 하지만 이 경우에 10만 * 10만으로 10^10 이기에 제한시간인 1초를 훨씬 넘긴다.

이 때문에 먼저 A 배열을 정렬한 이후 (시간 복잡도 nlogn) 값을 이진탐색을 통해 찾도록 한다.

처음에 틀린 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {



    public int BinarySearch(int arr[],int find,int start,int end){
        if(start<=end){
            if(find<arr[(start+end)/2]){
                end=(start+end)/2-1;
                return BinarySearch(arr,find,start,end);
            }
            else if(find==arr[(start+end)/2]){
               return 1;
            }
            else{
                start=(start+end)/2+1;
                return BinarySearch(arr,find,start,end);
            }
        }
        return 0;
    }


    public void solution() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int A[]=new int[n+1];



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

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

         int newA[]=Arrays.stream(A).sorted().toArray();


        int m = Integer.parseInt(br.readLine());

        int B[]=new int[m+1];

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

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


        for(int i=1;i<=m;i++){
            System.out.println(BinarySearch(newA,B[i],1,n));
        }

    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

무엇이 문제인지 몰라서 반례를 뒤졌다.

arr 배열의 인덱스를 1~n+1 로 설정하여 조금 더 편하게 했었는데

이러면 arr[0] 에 값이 0 이 들어가서 같이 정렬이 되는 문제점이 존재했다.

따라서 예상치 못한 에러가 함께 나타났다.

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {



    public int BinarySearch(int arr[],int find,int start,int end){
        if(start<=end){
            if(find<arr[(start+end)/2]){
                end=(start+end)/2-1;
                return BinarySearch(arr,find,start,end);
            }
            else if(find==arr[(start+end)/2]){
               return 1;
            }
            else{
                start=(start+end)/2+1;
                return BinarySearch(arr,find,start,end);
            }
        }
        return 0;
    }


    public void solution() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int A[]=new int[n];



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

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

         int newA[]=Arrays.stream(A).sorted().toArray();


        int m = Integer.parseInt(br.readLine());

        int B[]=new int[m];

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

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


        for(int i=0;i<m;i++){
            System.out.println(BinarySearch(newA,B[i],0,n-1));
        }

    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

헤멨던 이유

1)이진탐색:

start=(start+end)/2+1

이것을 초기에는

start=(start+end)/2 로만 사용했다.

그러다 보니까 종료 조건으로 넘어가질 않았기 때문이다(디버깅을 통해 그 사실을 깨달아서 늦게 풀었다.)

2) 정렬

또한 Arrays.steram.sorted(A) 에 대해서 시간 복잡도가 어느정도인지 알 수 없었기 때문에 o(nlogn) 일 것이라는 가정을 하고 진행했었다.