목록2024/04/18 (2)
Binaryseop
10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 접근 n이 최대 500,000, m이 최대 500,000이므로 선형 탐색을 사용한다면 최악의 경우 시간 복잡도가 O(n * m)가 될 것으로 예상됩니다. 따라서 이진 탐색을 활용하여 시간 복잡도를 O(m * logn)으로 줄일 수 있는 방법을 선택했습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import ..
1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 접근 n이 최대 100,000, m이 최대 100,000이므로 선형 탐색을 사용한다면 최악의 경우 시간 복잡도가 O(n * m)가 될 것으로 예상됩니다. 따라서 이진 탐색을 활용하여 시간 복잡도를 O(m * logn)으로 줄일 수 있는 방법을 선택했습니다. 풀이 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arra..