728x90
반응형
2276 - 암기왕
https://www.acmicpc.net/problem/2776
문제
연종이 하루 동안 본 정수들을 수첩1에 적어 놓았다.
그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종이에게 M개의 질문을 던졌다.
연종이가 봤다고 주장하는 수들을 수첩2에 적어 놓았다.
=> 수첩2에 적혀있는 순서대로, 각각의 수에 대하여 수첩1에 있으면 1/ 없으면 0 출력
입력
첫째 줄: 테스트케이스 개수 T
수첩 1에 적어 놓은 정수의 개수 N (1 <= N <= 1,000,000)
수첩 1에 적혀 있는 정수들이 입력으로 들어옴
수첩 2에 적어 놓은 정수의 개수 M (1 <= M <= 1,000,000)
수첩 2에 적어 있는 정수들이 입력으로 들어옴
출력
수첩 2에 적혀있는 M개의 숫자 순서대로 수첩 1에 있으면 1/ 없으면 0 출력
풀이
이진 탐색
리스트 정렬되어 있을 때 시간복잡도 $O(log N)$
static boolean binarySearch(int[] arr, int target) {
int lt = 0, rt = arr.length - 1;
while (lt <= rt) {
int mid = (lt + rt) / 2;
if (arr[mid] == target) return true;
else if (arr[mid] < target) lt = mid + 1;
else rt = mid - 1;
}
return false;
}
코드
import java.io.*;
import java.util.*;
// 암기왕
public class boj_2776 {
static boolean binarySearch(int[] arr, int target) {
int lt = 0, rt = arr.length - 1;
while (lt <= rt) {
int mid = (lt + rt) / 2;
if (arr[mid] == target) return true;
else if (arr[mid] < target) lt = mid + 1;
else rt = mid - 1;
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
int N = Integer.parseInt(br.readLine());
int[] note1 = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
note1[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(note1);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int target = Integer.parseInt(st.nextToken());
sb.append(binarySearch(note1, target) ? "1\n" : "0\n");
}
}
System.out.println(sb);
}
}
728x90
반응형
'💻 > 코딩테스트' 카테고리의 다른 글
[BOJ/] 백준 1966 - 프린터 큐 (Java) (1) | 2025.05.17 |
---|---|
[BOJ/] 백준 2161 - 카드 1 / 2164 - 카드 2 (Java) (0) | 2025.05.16 |
[BOJ/] 백준 2293 - 동전 1 / 2294 - 동전 2 (Java) (0) | 2025.05.16 |
[BOJ/] 백준 2606 - 바이러스 (Java) (0) | 2025.05.16 |
[BOJ/] 백준 1197 - 최소 스패닝 트리 (Java) (0) | 2025.05.16 |