[백준] 10816번 숫자 카드 2 / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
21. 이분 탐색
이분 탐색 알고리즘을 배워 봅시다.
이분 탐색 알고리즘을 배워 봅시다.
Java / Python
2. 숫자 카드 2
이분 탐색으로 값의 개수를 찾아 봅시다.
이번 문제는 숫자 카드 N개가 주어지고, 정수 M개가 주어질 때, 이 수가 적혀있는 숫자 카드가 몇개인지 구하는 프로그램을 작성하는 문제입니다.
- Java
import java.io.*;
import java.util.*;
public class Main{
static int[] arr;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
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 k = Integer.parseInt(st.nextToken());
bw.append((upper(k) - lower(k))+ " " );
}
bw.flush();
bw.close();
br.close();
}
private static int upper(int x) {
int start = 0, end = arr.length-1, mid;
while (start < end) {
mid = (start + end)/2;
if(arr[mid] > x) {
end = mid;
}else start = mid + 1;
}
if(arr[end] == x) end++;
return end;
}
private static int lower(int x) {
int start = 0, end = arr.length-1, mid;
while (start < end) {
mid = (start + end)/ 2;
if(arr[mid] >= x) {
end = mid;
}else start = mid + 1;
}
return end;
}
}
- Python
import sys
N = int(sys.stdin.readline())
arr_n = list(map(int,sys.stdin.readline().split()))
M = int(sys.stdin.readline())
arr_m = list(map(int,sys.stdin.readline().split()))
dic = dict()
for i in arr_n:
try :
dic[i] += 1
except:
dic[i] = 1
for i in arr_m:
try:
print(dic[i] , end = " ")
except:
print(0, end=" ")
Author And Source
이 문제에 관하여([백준] 10816번 숫자 카드 2 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-10816번-숫자-카드-2-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)