백준 10816번
https://www.acmicpc.net/problem/10816

---

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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보다 작거나 같다.

---

생각하기

백준에서 제공하는 테스트케이스에서는 정답이 나왔지만, 실제로 실행하면 오류가 나거나 오답이 나와서 진짜 멘탈이 반쯤 나갔었다..

결국에 백기를 들고 다른 분들의 풀이와 코드를 참고해서 공부를 하는게 맞겠다는 생각이 들었다.

숫자 카드 2 풀이

나는 처음에 Count방법과 HashMap의 getOrDefault() 함수를 이용해서 숫자를 카운팅하려고 했는데 머리가 나쁜 나머지 코딩에 실패 ㅠㅠ

풀이를 찾아보고나서 느낀거 였지만, 거의 다왔는데 조금 아깝다라는 생각이 들었다.

이분탐색 방법을 이용해서 풀어야 한다는 생각을 들었는데, 이전에 풀었던 문제와 달리 여러개의 원소 갯수를 파악하는 문제다 보니 같은 다른 값들은 어떻게 파악해야 되나 생각했다.

그래서 처음에 이분탐색의 범위를 조정해서 Counting을 해서 출력하려고 했는데,
결과는 실패..

풀이를 찾아보니 내가 이전에 사용한적 없는 이분탐색에서 Bound를 이용한 풀이가 정석이었다

풀이를 찾아보길 잘했다는 생각이 들었던게 한번도 생각해본적 없는 방식이었기때문에
새로운 풀이의 알고리즘을 학습할 수 있었다.

동작
동작은 이분탐색을 응용했다 생각하면 쉬울 것 같다.

먼저 List를 정렬해준다.
그 다음 List에서 내가 찾는 값의 갯수를 파악하기 위해서는 list 에서 내가 찾는 값의 가장낮은 index와 가장 높은 index 값을 빼주면 해당 값의 갯수를 파악할 수 있다.

해당 원리를 이용해서 2개의 함수를 만든다. 먼저 찾는 값의 가장 낮은 index를 파악하기 위한 함수 lowerBound와 가장 높은 index를 파악하는 upperBound 함수
이렇게 2개의 함수를 생성한다.

upperBound에서는 half 범위를 계속올려서 찾는 값 중 가장 높은 인덱스의 값을 반환하고

lowerBound에서는 half범위를 낮춰서 찾는 값 중 가장 낮은 인덱스의 값을 반환한다

이 인덱스값의 차이가 결국 중복된 원소의 갯수를 의미한다.

TMI

이분탐색을 할 줄 안다고 자신감이 붙은 상태였는데
조금만 문제를 꼬으거나 응용하면 풀지못하는 상태..

역시 자만은 좋지않다..

---

코드

UpperBound & LowerBound

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

public class Main {
	static final LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
	static final List<Integer> nlist = new ArrayList<>();

	private static int lowerBound(int num) {
		int min = 0;
		int max = nlist.size();

		// min과 max가 같아질 때 까지 반복
		while(min < max) {
			int half = (min + max) / 2;

			if(num <= nlist.get(half)) {
				max = half;
			}
			else {
				min = half + 1;
			}
		}

		return min;
	}

	private static int uppderBound(int num) {
		int min = 0;
		int max = nlist.size();

		// min과 max가 같아질 때 까지 반복
		while(min < max) {
			int half = (min + max) / 2;

			if(num < nlist.get(half)) {
				max = half;
			}
			else {
				min = half + 1;
			}
		}

		return min;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			nlist.add(Integer.parseInt(st.nextToken()));
		}

		Collections.sort(nlist);

		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			int num = Integer.parseInt(st.nextToken());			

			sb.append(uppderBound(num) - lowerBound(num) + " ");
		}
		
		System.out.println(sb);
	}
}

---

HashMap

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

public class Main {
	static final LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(st.nextToken());
			map.put(num, map.getOrDefault(num, 0) +1);
		}

		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			int num = Integer.parseInt(st.nextToken());			
			sb.append(map.getOrDefault(num, 0) + " ");
		}

		System.out.println(sb);
	}
}