반응형
🔺 문제
🔺 코드
- 틀림 (시간 복잡도 : O(MN) )
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
var br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr1 = new int[N];
var st = new StringTokenizer(br.readLine(), " ");
for(int i = 0 ; i< N ; i++) {
arr1[i] = Integer.parseInt(st.nextToken());
}
int M = Integer.parseInt(br.readLine());
int[] arr2 = new int[M];
st = new StringTokenizer(br.readLine(), " ");
for(int i = 0 ; i < M ; i++) {
int num = Integer.parseInt(st.nextToken());
for(int j = 0 ; j < N ; j++) {
if(num == arr1[j]) {
arr2[i] = 1;
}
}
}
for(int i : arr2) {
System.out.print(i + " ");
}
}
}
시간 초과가 뜸
- 정답 (시간 복잡도 : O((M+N)logN))
import java.util.*;
import java.io.*;
public class Main {
static int[] cards;
public static void main(String[] args) throws IOException {
var br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
cards = new int[N];
var st = new StringTokenizer(br.readLine(), " ");
for(int i = 0 ; i< N ; i++) {
cards[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(cards); // 이진 탐색을 위한 정렬
int M = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine(), " ");
for(int i = 0 ; i < M ; i++) {
int result = binarySearch(Integer.parseInt(st.nextToken()));
if(result != -1) sb.append(1 + " ");
else sb.append(0 + " ");
}
System.out.println(sb.toString());
}
// 이진 탐색
private static int binarySearch(int target) {
int left = 0;
int right = cards.length - 1;
int mid;
while(left <= right) {
mid = (left + right) / 2;
if(cards[mid] < target) left = mid + 1;
else if(cards[mid] > target) right = mid - 1;
else return mid;
}
return -1;
}
}
✅ 해결 아이디어
- 이진 탐색!
처음에 이진 탐색 아닌걸로 했다가 이진 탐색으로 컴백,,,
🔺 다른 풀이들
- 풀이1) Set 활용
Set - contains를 활용하셨다.
- 풀이2) Map 활용
Map - get을 활용하셨다.
💬 느낀 점
이진 탐색... 오랜만에 보았는데... 꼭 마스터해야겠다.. 복습 필수...
(참고)
✔ 이진 탐색 메소드에서 받는 인자가 약간씩 다른 풀이들
✔ 이진 탐색
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 7785번: 회사에 있는 사람 (0) | 2023.04.06 |
---|---|
[백준/JAVA] 14425번: 문자열 집합 (0) | 2023.04.06 |
[백준/JAVA] 2566번: 최댓값 (0) | 2023.04.05 |
[백준/JAVA] 2738번: 행렬 덧셈 (0) | 2023.04.05 |
[백준/JAVA] 5597번: 과제 안 내신 분..? (0) | 2023.04.05 |