백준 10816(숫자 카드2)

문제

---

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

 

 

 

 

 

 

 

풀이

---

풀이는 여러가지가 있다.

Java 에선 HashMap 을 사용하여 key 를 기준으로 동일한 key 가 들어오면 value++ 의 방식으로도 풀 수 있지만,

 

이분탐색으로 하는것이 공통언어에서의 풀이법이기 때문에 이분탐색을 이용하였다.

기존에 이분탐색은 같은 숫자에 대해서는 갯수를 찾지못한다.

이를 해결하기 위해 UpperBounds, LowerBounds 를 만들어 해결하였다.

 

UpperBounds의 코드다.

static int UpperBounds(List<Integer> cards, int left, int right, int num) {
		
		int mid;
		while(left <= right) {
			mid = (left + right) / 2;
			
			if(cards.get(mid) <= num) {
				left = mid + 1;
			}
			else {
				right = mid - 1;
			}			
		}	
		return right;
	}

같은 값이 나올때 left 값을 변경하여서 같은 값이 나오지 않을때까지의 right 값을 구한다.

같은 값이 있는 범위의 최대 index 값을 알아내기 위한 함수다.

 

LowerBounds의 코드다.

	static int LowerBounds(List<Integer> cards, int left, int right, int num) {
		int mid;
		while(left <= right) {
			mid = (left + right) / 2;
			
			if(cards.get(mid) >= num) {
				right = mid - 1;
			}
			else
				left = mid + 1;
		}
		
		return left;
	}

같은 값이 나올때 right 값을 변경하여서 같은 값이 나오지 않을때까지의 left 값을 구한다.

같은 값이 있는 범위의 최소 index 값을 알아내기 위한 함수다.

 

 

이렇게 나온 Upper - Lower + 1 을하면 같은 값을 가지는 숫자의 범위가 된다.

+1 을 하는 이유는 중학교수학에서 배운 Lower <= N <= Upper 에서 해당범위에 포함되는 숫자의 개수를 구하는 문제에서와 같은이유다. 

 

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	static int UpperBounds(List<Integer> cards, int left, int right, int num) {
		
		int mid;
		while(left <= right) {
			mid = (left + right) / 2;
			
			if(cards.get(mid) <= num) {
				left = mid + 1;
			}
			else {
				right = mid - 1;
			}			
		}
		 
		
		return right;
	}
	
	static int LowerBounds(List<Integer> cards, int left, int right, int num) {
		int mid;
		while(left <= right) {
			mid = (left + right) / 2;
			
			if(cards.get(mid) >= num) {
				right = mid - 1;
			}
			else
				left = mid + 1;
		}
		
		return left;
	}
	
	static int CountNumber(List<Integer> cards, int n, int num ) {
		
		int u = UpperBounds(cards, 0, n-1, num);
		int l = LowerBounds(cards, 0, n-1, num);
		
		return u - l + 1;
	}
	
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());		
		List<Integer> cards = new ArrayList<Integer>();
		
		String[] cardNumber = br.readLine().split("\\s"); 
		for(int i = 0 ; i < n ; i++) {
			cards.add(Integer.parseInt(cardNumber[i]));
		}
		Collections.sort(cards);
		
		int m = Integer.parseInt(br.readLine());		
		String[] nums = br.readLine().split("\\s");
		for(int i = 0 ; i < m ; i++) {
			sb.append(CountNumber(cards, n, Integer.parseInt(nums[i]))).append(" ");
		}
		System.out.println(sb);
	}
}