[백준/BOJ] 10816번 숫자 카드 2 자바 풀이

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

10816번: 숫자 카드 2

 

 

 

이분 탐색으로 수의 갯수를 세는건 익숙치 않아 조금 헷갈렸다.

하한선은 특정 숫자가 처음으로 나타나는 인덱스고,

상한선은 특정 숫자가 마지막으로 나타나는 인덱스 + 1이므로

상한선 - 하한선이 숫자의 갯수를 나타낸다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
	
		int N = Integer.parseInt(br.readLine());
		
		int arr[] = new int[N];
		
		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());
		for(int i=0;i<M;i++) {
			int key = Integer.parseInt(st.nextToken());
		
			sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
		}
		
		System.out.println(sb);
		br.close();
	}
	
	// 하한선 구하기
	static int lowerBound(int[] arr, int key) {
		int start = 0;
		int end = arr.length;
		int mid;
		
		while(start < end) { // 같아질 때까지
			mid = (start + end) / 2;
			
			if(arr[mid] >= key)
				end = mid;
			else 
				start = mid + 1;
		}
		
		return start;
	}
	
	// 상한선 구하기
	static int upperBound(int[]arr, int key) {
		int start = 0;
		int end = arr.length;
		int mid;
		
		while(start < end) { // 같아질 때까지
			mid = (start + end) / 2;
			
			if(arr[mid] > key)
				end = mid;
			else
				start = mid + 1;
		}
		
		return start;
	}

}

 

 

계수 정렬과 같은 방식의 풀이는 아래와 같다.

값의 범위가 -10,000,000 ~ 10,000,000 이므로

0부터 10,000,000의 인덱스는 양수의 갯수를 세고,

10,000,001부터 20,000,000의 인덱스는 음수의 갯수를 세도록 했다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int arr[] = new int[20000001];
		
		int N = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			int num = Integer.parseInt(st.nextToken());
			if(num < 0)
				arr[-num + 10000000]++;
			else
				arr[num]++;
		}
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<M;i++) {
			int num = Integer.parseInt(st.nextToken());
			if(num < 0)
				sb.append(arr[-num + 10000000]).append(' ');
			else
				sb.append(arr[num]).append(' ');
		}
		
		System.out.println(sb);
		br.close();
	}

}

 

 

위에가 이분 탐색이고, 아래가 숫자 count하는 방식인데,

수의 갯수를 세는 방식은 계수 정렬과 같은 방식으로 하는게 가장 빠른 것 같다.