Competition/Baekjoon
[백준] 10815번 자바 숫자카드
bisi
2020. 3. 31. 02:25
문제 출처
https://www.acmicpc.net/problem/10815
10815번: 숫자 카드
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이
www.acmicpc.net
접근 방식 및 풀이
- 이분탐색의 기초문제
- 시간초과가 안걸리는게 목표!
- HashSet으로도 구현할 수 있지만 이분탐색을 활용해보자~
소스 코드
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
long[] arra = new long[a];
for (int i = 0; i <a ; i++) {
arra[i] =sc.nextLong();
}
int b = sc.nextInt();
long[] arrb = new long[b];
for (int i = 0; i <b ; i++) {
arrb[i] =sc.nextLong();
}
Arrays.sort(arra);
int ans =0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i <b ; i++) {
int left = 0;
int right= a-1;
long val = arrb[i];
int mid =0;
// System.out.println("----- " + val);
while(left<=right){
mid =(left+right)/2;
// System.out.println("mid "+ mid + " arra[mid] " + arra[mid] + " val " + val);
if(arra[mid]>val){
right = mid-1;
ans = 0;
}else if(arra[mid]<val) {
left = mid+1;
ans = 0;
}else{
ans = 1;
break;
}
}
sb.append(ans+" ");
}
System.out.print(sb);
}
}
결과
