수 찾기

조소복·2022년 8월 11일

1920번 Java 백준 실버IV 자바

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

예제 출력 1

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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=new StringTokenizer(br.readLine());
	    StringBuilder sb=new StringBuilder();
	     
	    int N=Integer.parseInt(st.nextToken());
        int[] arr=new int[N];

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

        st=new StringTokenizer(br.readLine());
        int M=Integer.parseInt(st.nextToken());
        
        Arrays.sort(arr);

        st=new StringTokenizer(br.readLine());        
        for(int i=0;i<M;i++){
            int num=Integer.parseInt(st.nextToken());
            int left=0;
            int right=N-1;
            int mid=(left+right)/2;
            while(left<=right) {
            	mid=(left+right)/2;
            	
            	if(num<arr[mid]) {
            		right=mid-1;
            	}else if(num>arr[mid]){
            		left=mid+1;
            	}else {
            		break;
            	}
            }
            if(arr[mid]==num) {
            	sb.append("1\n");
            }else {
            	sb.append("0\n");
            }
        }

        System.out.println(sb);
	}

}

문제 자체는 단순히 배열안에 숫자가 있는지 확인하고 1 또는 0을 출력하는 문제이다.

하지만 코드도 단순하게 짠다면 시간초과가 발생할 수 있다. Arrays.asList(arr).contains()를 이용하여 배열안에 숫자가 있는지 확인하려고 했는데 시간초과가 발생하는 바람에 다른 방법을 알아봐야했다.

문제 밑에 있는 알고리즘 분류에서 이분탐색을 발견하고 이분탐색을 이용하여 문제를 풀었다.

이분탐색에 대해 간단하게 설명하면 정렬되어 있는 배열을 둘로 나누어 가운데 값과 비교하여 비교할 숫자들을 줄여나가는 방식이다.

즉, 가운데 값보다 찾으려는 값이 작다면 왼쪽으로 넘어가서 숫자를 찾아보고 반대라면 오른쪽으로 넘어가서 값을 찾아보는 방식을 반복하여 찾고자 하는 숫자가 있는지 확인하는 것이다.

left, right를 각각 제일 왼쪽, 오른쪽 인덱스로 초기화해주고 가운데값과 찾고자하는 값을 비교하여 mid보다 -1,+1로 이동시켜준다.

mid와 같은 값이라면 반복문을 끝내고 마지막으로 해당 인덱스에 있는 값과 찾고자하는 값이 같다면 1, 다르다면 0을 출력해준다.

다른 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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=new StringTokenizer(br.readLine());
	    StringBuilder sb=new StringBuilder();
	     
	    int N=Integer.parseInt(st.nextToken());
        int[] arr=new int[N];

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

        st=new StringTokenizer(br.readLine());
        int M=Integer.parseInt(st.nextToken());
        
        st=new StringTokenizer(br.readLine());        
        for(int i=0;i<M;i++) {
        	int num=Integer.parseInt(st.nextToken());
        	if(Arrays.binarySearch(arr,num)>=0) {
        		sb.append("1\n");
        	}else {
        		sb.append("0\n");
        	}
        }

        System.out.println(sb);
	}

}