문제

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

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

풀이

• 알고리즘 분류는 이분탐색이였지만 이거 해시 사용하면 더 빠르지 않을까..? 라는 생각에 Hash를 사용했다.
• 가독성은 훨씬 좋으나 메모리 및 시간면에서는 이분탐색보다 비효율적이였다.
• 베스트 코드를 보면서 java util 에서 이분 탐색 기능을 제공한다는 것을 알게되었다.
  • 단, 사용하려면 배열이 정렬되어있어야한다.
• 그 외에는 굉장히 간단한 코드였으므로 따로 풀이는 남기지 않겠다.

내가 제출한 코드

import java.util.*;

public class Main{
    static HashMap<Integer, Integer> map = new HashMap<>();
    
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        
        int hl = sc.nextInt();
        
        for(int i = 0; i < hl; i++){
            map.put(sc.nextInt(), 1);
        }
        
        int l = sc.nextInt();
        
        for(int i = 0; i < l; i++){
            int n = sc.nextInt();
            
            if(map.containsKey(n)) System.out.println(1);
            else System.out.println(0);
        }
    }
}

베스트 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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));
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		
		// 배열은 반드시 정렬되어있어야한다.
		Arrays.sort(arr);
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine(), " ");
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < M; i++) {
			
			// 찾고자 하는 값이 있을 경우 1, 없을 경우 0을 출력해야한다.
			if(Arrays.binarySearch(arr, Integer.parseInt(st.nextToken())) >= 0) {
				sb.append(1).append('\\n');
			}
			else {
				sb.append(0).append('\\n');
			}
		}
		System.out.println(sb);
	}
	
 
}