[BOJ 10816] 숫자 카드 2

문제

---

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

이 문제는 푸는 방식이 2가지가 있는데 바이너리 서치와 Map을 이용한 풀이다.

[풀이 코드]

---

이 코드는 바이너리서치를 이용한 코드다.

import java.io.*;
import java.util.*;

public class Main {
	static int N, M;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		int[] n_arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			n_arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(n_arr);
		
		M = Integer.parseInt(br.readLine());
		int[] m_arr = new int[M];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int target = Integer.parseInt(st.nextToken());
			sb.append(right(n_arr, target) - left(n_arr, target) + " ");
		}
		System.out.println(sb);
	}
	static int left(int[] arr, int target) {
		int left = 0;
		int right = N;
		while(left < right) {
			int mid = (left+right)/2;
			
			if(arr[mid]>=target) {
				right = mid;
			}else {
				left = mid+1;
			}
		}
		return left;
	}
	
	static int right(int[] arr, int target) {
		int left = 0;
		int right = N;
		while(left < right) {
			int mid = (left+right)/2;
			
			if(arr[mid]>target) {
				right = mid;
			}else {
				left = mid+1;
			}
		}
		return left;
	}
}

찾을려고 하는 target이 여러 개가 있으면
left 메서드는 찾고자 하는 target 값이 처음 등장하는 위치를 반환한다.
right 메서드는 target보다 큰 값이 처음 나오는 위치를 반환한다.
즉, right-left는 target 값이 배열에 등장한 총 횟수가 된다.

예를 들어
arr = [1, 2, 3, 3, 3, 4, 5]이고, target이 3이라고 했을 때,
left(arr, target)은 처음 3이 나온 위치 2를 반환하고,
right(arr, target)은 마지막 3이 나온 위치에 1을 더한 5를 반환한다.

바이너리 서치 문제 유형을 많이 풀어보자.

[풀이 코드]

---

이 코드는 Map을 이용한 코드다.

import java.util.*;
import java.io.*;

public class test {
    public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Map<Integer, Integer> map = new HashMap<>();
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int key = Integer.parseInt(st.nextToken());
			map.put(key, map.getOrDefault(key, 0) + 1);
		}
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int target = Integer.parseInt(st.nextToken());
			sb.append(map.getOrDefault(target, 0) + " ");
		}
		System.out.println(sb);
    }
}

Map을 이용해 Key와 Value를 넣어주고, 값을 찾아주는 단순한 문제다.
여기서 알아야 할 함수는 Map 라이브러리에 있는 getOrDefault 함수이다.

이 함수는 다음과 같이 동작한다.
key가 존재하면 해당하는 값을 반환하고,
존재하지 않으면 defaultValue를 반환한다.

즉, map.getOrDefault(target, 0)은 target이 존재하면 그 값을 반환하고, 없으면 0을 반환하게 된다.