https://www.acmicpc.net/problem/1920
문제
풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
StringBuffer pr = new StringBuffer();
int n = kb.nextInt();
int[] arrN = new int[n];
for(int i=0; i<n; i++) {
arrN[i] = kb.nextInt();
}
int m = kb.nextInt();
int[] arrM = new int[m];
for(int i=0; i<m; i++) {
arrM[i] = kb.nextInt();
}
Arrays.sort(arrN);
for(int x : arrM) {
int min = 0;
int max = n-1;
int answer = 0;
while(min <= max) {
int mid = (min + max) / 2;
if(arrN[mid] == x) {
answer = 1;
break;
}else if(arrN[mid] < x) {
min = mid + 1;
}else {
max = mid - 1;
}
}
pr.append(answer).append("\n");
}
System.out.print(pr);
}
}
시간 제한만 없다면 문제를 푸는데 전혀 어려움은 없을 것이다. 가장 대표적인 것은 ArrayList로 받은 다음 contains 메소드를 사용하면 된다. 이 경우 순차 탐색으로 시간이 오래 걸린다는 단점을 가지고 있다. 실제로 이렇게 풀면 시간 초과가 나오며 틀리게 된다.
탐색에서 시간을 줄일 수 있는 방법은 이분 탐색(Binary Search)을 하는 것이다. 이분 탐색을 구현만 해주면 전혀 어려운 문제는 아니었다.
'문제 풀이 > 백준' 카테고리의 다른 글
[백준] 1343번. 폴리오미노 (JAVA) (0) | 2024.01.15 |
---|---|
[백준] 1806번. 부분합 (JAVA) (0) | 2023.01.12 |
[백준] 1654번. 랜선 자르기 (JAVA) (1) | 2023.01.11 |
[백준] 2839번. 설탕 배달 (JAVA) (0) | 2023.01.11 |
[백준] 1929번. 소수 구하기 (JAVA) (0) | 2023.01.11 |