백준
[백준] 10816 숫자 카드 2_ JAVA
채니◟( ˘ ³˘)◞
2023. 7. 11. 17:15
● 문제
● 풀이
이는 10815 숫자 카드와 비슷한 문제이다.
다른 점은 상근이의 숫자 카드에서 주어진 M개 중 그 수가 적혀있는 숫자 카드의 개수를 구하는 것이다.
첫번째 풀이
시간 초과를 방지 하기 위해 일단 이분 탐색을 사용하였고, 배열에 존재하는 수 일때 개수를 구하기 위해 for문을 돌렸는데, 아마 이곳에서 시간 초과가 난 것 같다.
import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
StringBuilder sb = new StringBuilder();
int m = in.nextInt();
for (int i = 0; i < m; i++) {
int k = in.nextInt();
int count =0;
if (binarySearch(arr, k) >= 0) {
for(int num : arr){
if(num == k){
count++;
}
}
sb.append(count).append(' ');
} else
sb.append('0').append(' ');
}
System.out.println(sb);
}
private static int binarySearch(int[] arr, int key) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (key < arr[mid]) {
right = mid - 1;
} else if (key > arr[mid]) {
left = mid + 1;
} else
return mid;
}
return -1;
}
}
출처 : https://st-lab.tistory.com/267
전 10815 숫자 카드 문제에서는 arr[mid] 값과 key 값이 동일하면 반환을 했었다.
하지만, 이번 문제의 경우 우리가 고려할 점은 '중복 원소의 개수'를 알아내는 것이다.
중복 원소의 왼쪽 끝 값과 오른쪽 끝 값을 각각 알아내는 것이다.
첫번째 문제 풀이 (이분 탐색)
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
for(int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr); // 이분 탐색을 하기 위해서는 반드시 정렬되어있어야 한다.
int M = in.nextInt();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < M; i++) {
int key = in.nextInt();
// upperBound와 lowerBound의 차이 값을 구한다.
sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
}
System.out.println(sb);
}
private static int lowerBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length;
// lo가 hi랑 같아질 때 까지 반복
while (lo < hi) {
int mid = (lo + hi) / 2; // 중간위치를 구한다.
/*
* key 값이 중간 위치의 값보다 작거나 같을 경우
*
* (중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다.)
*/
if (key <= arr[mid]) {
hi = mid;
}
else {
lo = mid + 1;
}
}
return lo;
}
private static int upperBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length;
// lo가 hi랑 같아질 때 까지 반복
while (lo < hi) {
int mid = (lo + hi) / 2; // 중간위치를 구한다.
// key값이 중간 위치의 값보다 작을 경우
if (key < arr[mid]) {
hi = mid;
}
// 중복원소의 경우 else에서 처리된다.
else {
lo = mid + 1;
}
}
return lo;
}
}
두번째 문제 풀이 ( 해시맵)
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
HashMap<Integer, Integer> map = new HashMap<>();
int N = scanner.nextInt();
scanner.nextLine();
StringTokenizer st = new StringTokenizer(scanner.nextLine(), " ");
for (int i = 0; i < N; i++) {
int key = Integer.parseInt(st.nextToken());
map.put(key, map.getOrDefault(key, 0) + 1);
}
int M = scanner.nextInt();
scanner.nextLine();
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(scanner.nextLine(), " ");
for (int i = 0; i < M; i++) {
int key = Integer.parseInt(st.nextToken());
sb.append(map.getOrDefault(key, 0)).append(' ');
}
System.out.println(sb);
}
}