[백준] 10815번 : 숫자 카드(JAVA)

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

10815번: 숫자 카드

풀이

이문제를 보고 간단하게 contains로 풀면되겠네 라고 하고 풀어봤습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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());
		
		ArrayList<Integer> arr = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr.add(Integer.parseInt(st.nextToken()));
		}
		
		int m = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < m; i++) {
			if(arr.contains(Integer.parseInt(st.nextToken())) == true) {
				sb.append(1);
			}
			else {
				sb.append(0);
			}
			sb.append(" ");
		}
		System.out.println(sb);
	}
}

그런... 시간초과

이번에 배우게된 이분탐색을 활용해서 하게되면 시간초과가 뜨지않고 해결할 수 있습니다.

 

arr배열에 값을 입력받아 저장합니다.

그 후 입력받은 숫자를 받고 이분탐색을 통하여 찾아 있으면 1을 return 없으면 0을 return 해주면 됩니다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 size = Integer.parseInt(br.readLine());
		
		int[] arr = new int[size];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < size; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		size = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		while(size --> 0) {
			sb.append(binary_search(arr, 0, arr.length - 1, Integer.parseInt(st.nextToken()))).append(" ");
		}
		System.out.print(sb);
	}
	
	public static int binary_search(int[] arr, int start, int end, int n) {
		while(start <= end) {
			int mid = (start + end) / 2;
			
			if(arr[mid] == n) {
				return 1;
			}
			
			if(n < arr[mid]) {
				end = mid - 1;
			}
			else {
				start = mid + 1;
			}
		}
		return 0;
	}
}