문제
연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.
입력
첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에 ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.
출력
‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.
시간 제한 : 2초
메모리 제한 :256 MB
문제의 조건 : N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)
- 배열을 정렬하여도 N과 M을 전부 비교하면 최악의 경우 1000000 * 1000000 번 비교를 하게 됩니다. O(N^2) ( 약 1조번의 반복으로 시간 제한에 걸리게 됩니다. )
- 따라서 이분 탐색을 사용하여야 시간 제한 내에 성공할 수 있습니다. O(logN)
풀이
이분 탐색을 사용하기 위해 우선 비교할 배열인 수첩 1을 정렬하였습니다.
// 이분 탐색을 위해 배열을 정렬해줍니다.
Arrays.sort(arr_1);이후 수첩 2 배열을 순회하며 수첩 1 배열에 이분탐색을 하였습니다.
for (int i = 0; i < M; i++) {
// bufferedWriter.append()는 결과를 출력에 담는 함수입니다.
// arr_2의 각 원소를 기준으로 arr_1을 이분탐색했습니다.
bufferedWriter.append(binarySearch(arr_1, arr_2[i]) + "\\n");
}이분탐색 코드
// int[] target : 탐색할 배열, find : 찾을 수
static int binarySearch(int[] target, int find) {
// left , right
int l = 0;
int r = target.length - 1;
while (l <= r) {
// 중간 값을 비교
int mid = (l+r)/2;
// 같은 값을 찾은 경우 1을 리턴
if (find == target[mid]) {
return 1;
}
// 중간 값보다 찾는 수가 작은 경우
if (find < target[mid]) {
r = mid - 1;
}
else // if ( find > target[mid] ) 중간 값보다 찾는 수가 큰 경우
{
l = mid + 1;
}
}
// 찾지 못한 경우
return 0;
}전체 코드
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
/**
* 암기왕
*/
public class BOJ2776 {
static int T;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
T = Integer.parseInt(bufferedReader.readLine());
while (T-- > 0) {
int arr_1[], arr_2[];
// input
int N = Integer.parseInt(bufferedReader.readLine());
String[] s = bufferedReader.readLine().split(" ");
// 수첩 1 초기화 및 입력 값 저장
arr_1 = new int[N];
for (int i = 0; i < N; i++) {
arr_1[i] = Integer.parseInt(s[i]);
}
// input
int M = Integer.parseInt(bufferedReader.readLine());
s = bufferedReader.readLine().split(" ");
// 수첩 2 초기화 및 입력 값 저장
arr_2 = new int[M];
for (int i = 0; i < M; i++) {
arr_2[i] = Integer.parseInt(s[i]);
}
// 이분 탐색을 위해 배열을 정렬해줍니다.
Arrays.sort(arr_1);
for (int i = 0; i < M; i++) {
// bufferedWriter.append()는 결과를 출력에 담는 함수입니다.
// arr_2의 각 원소를 기준으로 arr_1을 이분탐색했습니다.
bufferedWriter.append(binarySearch(arr_1, arr_2[i]) + "\n");
}
}
// 출력
bufferedWriter.flush();
// 종료
bufferedReader.close();
bufferedWriter.close();
}
// int[] target : 탐색할 배열, find : 찾을 수
static int binarySearch(int[] target, int find) {
// left , right
int l = 0;
int r = target.length - 1;
while (l <= r) {
// 중간 값을 비교
int mid = (l+r)/2;
// 같은 값을 찾은 경우 1을 리턴
if (find == target[mid]) {
return 1;
}
// 중간 값보다 찾는 수가 작은 경우
if (find < target[mid]) {
r = mid - 1;
}
else // if ( find > target[mid] ) 중간 값보다 찾는 수가 큰 경우
{
l = mid + 1;
}
}
// 찾지 못한 경우
return 0;
}
}
https://www.acmicpc.net/problem/2776
2776번: 암기왕
연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며,
www.acmicpc.net
'PS > 백준' 카테고리의 다른 글
| [ BOJ 2776 ] 암기왕 ( JAVA ) (0) | 2023.08.02 |
|---|---|
| [ BOJ 3649 ] 로봇 프로젝트 ( JAVA ) (0) | 2023.07.31 |
| [ BOJ 1966 ] 프린터 큐 ( JAVA ) (0) | 2023.07.26 |
| [ BOJ 16234 ] 인구 이동 ( JAVA ) (0) | 2023.07.24 |
| [ BOJ 4179 ] 불! ( JAVA ) (0) | 2023.05.26 |
