Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

21. 이분 탐색

이분 탐색 알고리즘을 배워 봅시다.

Java / Python

2. 숫자 카드 2

10816번

이분 탐색으로 값의 개수를 찾아 봅시다.

이번 문제는 숫자 카드 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=" ")