https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
//이진탐색 scanner 사용 버전
public class binarySearchPractice06 {
public static int binarySearch(int[] array, int target){
if (array == null || array.length == 0){
return -1;
}
int left = 0;
int right = array.length - 1;
while (left <= right){
int mid = left + (right - left)/ 2; //오버플로우 방지
if (target == array[mid]){
return mid;
} else if (target < array[mid]) {
right = mid - 1;
}else {
left = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] array = new int[N];
for (int i = 0; i < N; i++) {
array[i] = sc.nextInt();
}
Arrays.sort(array);
int M = sc.nextInt();
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < M; i++) {
if(binarySearch(array, sc.nextInt()) >= 0){
stringBuilder.append(1).append("\n");
}else {
stringBuilder.append(0).append("\n");
}
}
System.out.println(stringBuilder);
}
}
//이진탐색 BufferedReader사용 버전
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int inputDataN = Integer.parseInt(br.readLine()); //입력받음
int[] array = new int[inputDataN]; //입력받은 값으로 배열 생성
StringTokenizer st = new StringTokenizer(br.readLine()); //문자열 잘라냄
for (int i = 0; i < inputDataN; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
//오름차순 정렬
Arrays.sort(array);
int inputDataM = Integer.parseInt(br.readLine()); //입력받음
StringBuilder stringBuilder = new StringBuilder(); //결과 저장을 위함
st = new StringTokenizer(br.readLine());
for (int i = 0; i < inputDataM; i++) {
int check = Arrays.binarySearch(array, Integer.parseInt(st.nextToken()));
if (check >= 0){
stringBuilder.append(1 + "\n");
}else {
stringBuilder.append(0 + "\n");
}
}
System.out.println(stringBuilder);
}
}
참고link
https://st-lab.tistory.com/261
[백준] 1920번 : 수 찾기 - JAVA [자바]
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음
st-lab.tistory.com
'Study for Backend > Algorithm' 카테고리의 다른 글
[Algorithm 기초] 그리디 알고리즘 (0) | 2024.03.03 |
---|---|
[Algorithm 기초] 투 포인터 (4) | 2024.02.25 |
[Algorithm 기초] 이진 탐색 (0) | 2024.02.24 |
[Algorithm 기초] 기수 정렬, 계수 정렬, 셀 정렬 (0) | 2024.02.22 |
[Algorithm 기초연습] 백준 2750 수 정렬하기 (0) | 2024.02.22 |