-
백준 10815(JAVA) - 숫자 카드Algorithm 2022. 11. 24. 17:10728x90
백준 10815 숫자 카드 문제이다. 이 문제는 실버가 아니라면 단순히 브루트포스법으로 풀었을 듯 하지만, 실버이기 때문에 단순하지 않게 하지 않고 이분 탐색을 사용했다.
※ 알고리즘
1. 배열로 N개의 수를 입력받는다.
2. 배열을 정렬한다. sorting 사용
3. M개의 수를 num 변수에 입력받고 각각을 이분 탐색 함수 안에서 배열의 수와 num 변수를 비교하여 체크하고 1 or 0을 출력한다.
4. 총 M개의 1 or 0을 출력시킨다.
package selftest; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main_10815 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int N = Integer.parseInt(br.readLine()); int arr[] = new int[N]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i = 0; i<N; i++) { arr[i] = Integer.parseInt(st.nextToken()); } Arrays.sort(arr); int M = Integer.parseInt(br.readLine()); st = new StringTokenizer(br.readLine()); for(int i = 0; i<M; i++) { int num = Integer.parseInt(st.nextToken()); sb.append(binarySearch(arr, N, num) + " "); } System.out.println(sb.toString()); } public static int binarySearch(int[] arr, int n, int target) { int low = 0; int high = n-1; int mid = 0; while(low <= high) { mid = (low + high) / 2; if(arr[mid] == target) { return 1; } if(arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return 0; } }
이렇게 이분탐색을 이용하면 시간초과 없이 깔끔하게 해결가능!!!
728x90'Algorithm' 카테고리의 다른 글
백준 10448(JAVA) - 유레카 이론 (0) 2022.11.24 백준 15953(JAVA) - 상금헌터 (0) 2022.11.24 백준 2751(JAVA) - 수 정렬하기2 (0) 2022.11.22 백준 2810(JAVA) - 컵홀더 (0) 2022.11.17 백준 2512(JAVA) - 예산 (0) 2022.11.15