백준 10816. 숫자카드2

🅰 백준 10816. 숫자카드2

10816번: 숫자 카드 2

✏️ 문제 풀이

• HashMap을 이용하여 중복되는 카드의 개수를 저장해주었다.
• 그 외에는 숫자카드1과 마찬가지로 이분탐색을 하면서 재귀를 구현하여서 문제를 풀었다.

✏️ 소스코드

package divideandconquer;

import java.util.*;
import java.io.*;
/*HaseMap을 이용하여 key,value값을 저장해주었다.*/
public class Main_실버4_10816_숫자카드2 {
	private static int start, middle, end;
	private static StringBuilder sb = new StringBuilder();
	private static HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
	private static ArrayList<Integer> nArr = new ArrayList<Integer>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int input = Integer.parseInt(st.nextToken());
			if (hm.containsKey(input)) {
				hm.put(input, hm.get(input) + 1);
			} else {
				hm.put(input, 1);
				nArr.add(input);
			}
		}
		Collections.sort(nArr);
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			start = 0;
			end = nArr.size() - 1;
			middle = start + end / 2;
			int input = Integer.parseInt(st.nextToken());
			search(input);
		}
		System.out.println(sb);
	}

	private static void search(int input) {

		if (start > end) {
			sb.append(0+" ");
			return;
		}
		if (nArr.get(middle) == input) {
			sb.append(hm.get(input)+" ");
			return;
		}
		if (nArr.get(middle) < input) {
			start = middle + 1;
			middle = (start + end) / 2;
		} else {
			end = middle - 1;
			middle = (start + end) / 2;
		}
		search(input);
	}
}

 

✅ 후기

•