이분탐색/삼분탐색 #10816: 숫자 카드2 [JAVA]

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

 

 

---

 

 

 

문제 접근

 

 

 

 

3가지 방법으로 풀 수 있다.

 

 

 

 

 

1. 이진 탐색 활용 - upper bound, lower bound 이용

 

 

 

이해가 안되서 한참 들여다봤다..

 

 

 

이분탐색 활용 버전인 upper bound, lower bound를 구해서 중복 원소에 대한 길이를 찾아야 하는 문제이다.

 

이분 탐색에서 원래는 arr[mid]==key 이면 return mid 해서 binary search 가 끝났지만

 

lower bound는 arr[mid]==key 이어도 탐색이 끝나지 않고 같을 때의 하한을 찾아야하기 때문에 hi=mid-1 로 두고 lo==hi일때까지 탐색해야한다. (구간을 점점 좁혀서 lo==hi가 될 때까지)

 

 

[ 참고 ] https://st-lab.tistory.com/267

 

 

 

 

그리고, 첫 hi 인덱스 값 배열의 길이-1 이 아닌 배열의 길이로 두는 이유를 몰랐는데 아래 블로그 글을 보고 이해했다.

 

[ 참고 ] https://innovation123.tistory.com/65

 

 

 

 

 

 

 

 

2. counting 정렬

 

 

 

 

counting sort

 

: 수의 범위를 배열의 인덱스로 삼아 수의 개수를 카운팅

 

수의 개수는 얼마 없는데 범위가 크면 메모리 낭비

 

 

 

 

 

 

 

3. HashMap 이용

 

 

은 생략

 

 

 

 

 

 

 

코드

 

 

 

 

1. 이진 탐색 활용 - upper bound, lower bound 이용

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		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());
		StringBuilder sb = new StringBuilder();
		while (m-- > 0) {

			int key = Integer.parseInt(st.nextToken());

			sb.append(upper(key) - lower(key)).append(' ');

		}

		System.out.println(sb);
	}

	static int upper(int key) {

		int low = 0;
		int hi = arr.length;

		while (low < hi) {

			int mid = (low + hi) / 2;

			if (key >= arr[mid]) {
				low = mid + 1;
			} else {
				hi = mid;
			}
		}

		return low;
	}

	static int lower(int key) {

		int low = 0;
		int hi = arr.length;

		while (low < hi) {

			int mid = (low + hi) / 2;

			if (key <= arr[mid]) {
				hi = mid;
			} else {
				low = mid + 1;
			}
		}

		return low;
	}

}

 

 

 

 

 

 

 

 

 

 

2. counting 정렬

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		int[] counting = new int[20000001];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			counting[Integer.parseInt(st.nextToken()) + 10000000]++;
		}

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

		st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		while (m-- > 0) {
			int cnt = counting[Integer.parseInt(st.nextToken()) + 10000000];
			sb.append(cnt).append(' ');
		}

		System.out.println(sb);
	}

}

 

 

 

 

 

 

 

 

 

3. HashMap 사용

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		Map<Integer, Integer> map = new HashMap<>();

		StringTokenizer st = new StringTokenizer(br.readLine());
		while (n-- > 0) {
			int num = Integer.parseInt(st.nextToken());
			if (map.containsKey(num)) {
				map.put(num, map.get(num) + 1);
			} else {
				map.put(num, 1);
			}
		}

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

		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		while (m-- > 0) {
			int num = Integer.parseInt(st.nextToken());
			if (!map.containsKey(num)) {
				sb.append(0).append(' ');
			} else {
				sb.append(map.get(num)).append(' ');
			}
		}

		System.out.println(sb);
	}
}