문제 💁🏻♂️
해결 과정
문제를 보자마자 든 생각은 테스트 케이스가 여러 개 존재할 수 있고, N의 범위가 크다는 점에서 2중 for문을 사용하면 안된다는 생각이 들었다.
사고 과정 (HashSet) ❗️
어떤 숫자들의 모임에서 특정 숫자가 존재하는지 여부를 판단할 때, 어떤 자료구조가 적합할까? 그것은 바로 Set & Dictionary(= Map) 이다. 자바에서는 컬렉션 프레임워크에 HashSet, HashMap 이 존재하고, java.util 패키지에 들어있기 때문에 반드시 import 해주고 사용해야 한다.
따라서, 이 문제를 간단하게 해결하는 방법은 HashSet 변수에 "수첩 1"의 숫자들을 모두 저장한 다음에, "수첩 2"에 들어있는 숫자들을 순회하면서 HashSet 변수에 존재 여부를 판단하면 된다. 특히, "HashSet"의 contains() 메서드는 시간복잡도 O(1)을 가지므로, 상당히 빠르게 원소의 존재 여부를 판단할 수 있다. 이렇게 코드를 구현하여 제출했더니 정답 판정을 받았지만, 알고리즘 분류에 이분 탐색 도 있었다. 그래서 한번 이분 탐색으로도 문제를 풀어보려고 한다.
사고 과정 (이분 탐색) ‼️
이분 탐색의 로직은 어느 정도 정해져 있지만, 파이썬에서 자바로 코테 언어를 바꾸면서 한번 자바 문법대로 작성해보았다. 이 문제를 풀기 위한 이분 탐색 로직은 다음과 같다.
private static boolean bs(int target) {
int left = 0;
int right = N - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target)
return true;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return false;
}left와 right 인덱스가 서로 엇갈리는 순간 while 반복문은 종료된다. 또한, 배열 속 mid 인덱스를 가진 숫자와 target 값이 정확하게 일치하게 되면 true, 그게 아니라면 false를 반환하도록 설계했다. 이 방법으로 코드를 풀이해도 문제는 패스하며, HashSet 자료구조를 사용했을 때보다 살짝 느린 결과를 확인할 수 있었다.
코드
정답 코드 (HashSet)
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int T, N, M;
static Set<Integer> s;
public static void main(String[] args) throws IOException {
T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
s = new HashSet<>();
for (int i = 0; i < N; i++)
s.add(Integer.parseInt(st.nextToken()));
M = Integer.parseInt(br. readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(st.nextToken());
if (s.contains(num))
sb.append("1").append('\n');
else
sb.append("0").append('\n');
}
}
System.out.println(sb.toString());
}
}
정답 코드 (이분 탐색)
import java.util.*;
import java.io.*;
public class Main_1 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int T, N, M;
static int[] arr;
public static void main(String[] args) throws IOException {
T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
arr = new int[N];
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
Arrays.sort(arr); // 이분 탐색을 위한 정렬
M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int target = Integer.parseInt(st.nextToken());
if (bs(target)) sb.append("1").append('\n');
else sb.append("0").append('\n');
}
}
System.out.println(sb.toString());
}
private static boolean bs(int target) {
int left = 0;
int right = N - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target)
return true;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
}Reference
