[백준 1920] 수 찾기_자바Java
1. 문제
https://www.acmicpc.net/problem/1920
2. 풀이
재귀를 이용한 Binary Search로 문제를 해결했다.
문제에서 N의 범위는 (1 ≤ N ≤ 100,000), M의 범위는 (1 ≤ M ≤ 100,000)로 나타냈기 때문에 brute force로 풀면 O(N^2)이라 시간초과가 난다.
Binary Search(이진탐색, 이분탐색)
- 사전조건: 배열이 정렬되어 있어야한다.
- N 크기의 arr[] 배열이 있다고 가정한다.
- index의 최대 범위를 지정한다. 0 ~ N-1이므로 left 값은 0, right 값은 N-1
- 코드에서는 left가 start, right가 end로 쓰인다.
- left와 right의 중간값인 mid를 구한다. -
(left + right) / 2
- 찾고자 하는 값과 arr[mid] 값이 같은지 비교하고 범위를 조정한다.
4-1. 같으면 return mid;
4-2. 찾고자 하는 값이 arr[mid]보다 작으면 범위를 왼쪽 범위로 옮겨준다.
=>right = mid - 1;
4-3. 찾고자 하는 값이 arr[mid]보다 크면 범위를 오른쪽으로 옮겨준다.
=>left = mid + 1;
- 조정된 범위로 다시 search 함수를 호출한다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int[] NList;
public static StringBuilder sb;
public static StringTokenizer st;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
sb = new StringBuilder();
// Setting about N
int N = Integer.parseInt(in.readLine());
NList = new int[N];
st = new StringTokenizer(in.readLine(), " ");
for (int i = 0; i < N; i++) {
NList[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(NList);
// Setting about M
int M = Integer.parseInt(in.readLine());
st = new StringTokenizer(in.readLine(), " ");
for (int i = 0; i < M; i++) {
int result = search(Integer.parseInt(st.nextToken()), 0, N - 1);
sb.append(result == -1 ? 0 : 1).append("\n");
}
out.write(sb.toString());
out.close();
in.close();
}
private static int search(int num, int start, int end) {
int mid;
while (start <= end) {
mid = (start + end) / 2;
if (num == NList[mid]) {
return mid;
} else if (num < NList[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
}
Author And Source
이 문제에 관하여([백준 1920] 수 찾기_자바Java), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoonjy1106/백준-7576-토마토자바Java-o0wpe7e2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)