자바 백준 10816번 문제 : 숫자 카드 2

문제 출처 : https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

 

문제 :

 

풀이 :

 

소스코드 :

import java.util.*;
import java.io.*;
class Main {
	public StringBuilder solution(int n, int[] nArr, int m, int[] mArr) {
		StringBuilder sb = new StringBuilder();
		// nArr가 오름차순 정렬된 TreeMap에 저장 (key, value) = (숫자, 반복되는 횟수)
		SortedMap<Integer, Integer> map = new TreeMap<>();
		for(int x : nArr) map.put(x, map.getOrDefault(x, 0) + 1);
		// map에서 key만 가져온 keyArr 생성
		int size = map.size();
		int[] keyArr = new int[size];
		int[] ansArr = new int[m];
		int j = 0;
		for(Map.Entry<Integer, Integer> ent : map.entrySet()) {
			keyArr[j] = ent.getKey();
			j++;
		}
		// keyArr와 mArr의 이분탐색, 해당 key 찾은 다음 map에서 value 가져오기
		for (int i=0; i<m; i++) {
			int lt = 0, rt = size - 1;
			while (lt <= rt) {
				int mid = (lt + rt) / 2;
				if (keyArr[mid] == mArr[i]) {
					ansArr[i] = map.get(mArr[i]);
					break;
				}
				if (keyArr[mid] > mArr[i]) rt = mid - 1;
				else lt = mid + 1;
			}
		}
		// ansArr 출력
		for(int x : ansArr) {
			sb.append(x).append(" ");
		}
		return sb;
	}
	public static void main(String[] args) throws IOException {
		Main T = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] nArr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) nArr[i] = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(br.readLine());
		int[] mArr = new int[m];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<m; i++) mArr[i] = Integer.parseInt(st.nextToken());
		System.out.println(T.solution(n, nArr, m, mArr));
	}
}