Baekjoon10816: 숫자 카드2, 카운팅 배열 & 이분탐색

숫자 카드 2 

1 초

256 MB

49590

17969

12742

35.725%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

풀이1

카운팅 배열을 사용할 수 있다.

입력 받은 값에 100000000을 더해서 양수의 형태로 배열 안에 카운팅하고

M에서 입력받은 값들에도 10000000을 더해 index의 값을 찾아주면 된다

 

Buffer 사용

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int[] arr = new int[20000001]; //숫자의 최대 개수
		for(int i=0; i<N;i++) {
			arr[Integer.parseInt(st.nextToken())+10000000]++; //양수저장
		}
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<M;i++) { //값 불러오기
			sb.append(arr[Integer.parseInt(st.nextToken())+10000000]+" ");
		}
		System.out.print(sb.toString());
}}

Scanner 사용

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner s=new Scanner(System.in);
		StringBuilder sb=new StringBuilder();//스트링빌더로 시간초과 방지
		int[] arr=new int[20000001];
		for(int i=s.nextInt();i>0;i--) arr[s.nextInt()+10000000]++;
		for(int i=s.nextInt();i>0;i--) sb.append(arr[s.nextInt()+10000000]+" ");
		System.out.print(sb);
	}
}

 

풀이2

중복된 수가 있을 때 두 개의 탐색포인트를 이용해 이분 탐색을 진행한다. (lower bound, upper bound)

예시 문제를 살펴보면 다음과 같다.

6 3 2 10 10 10 -10 -10 7 3

정렬을 수행하면

-10 -10 2 3 3 6 7 10 10 10

10의 개수를 찾는다고 가정해보자.

lower bound

숫자 N을 찾을 때, N이 시작하는 index이다.

위 정렬된 수들에서 10 10 10이 있는데 가장 왼쪽에 있는 10의 위치가 lower bound이다.

이분탐색, pivot 정렬의 방식으로 찾는다.

배열의 끝 값은 9이므로 9 ÷ 2 = 4 index에서 시작한다. 

-10

-10

2

3

3

6

7

10

10

10

0~9 index 범위 → 중간값 index 4의 숫자 3은 10보다 작다 → index 4의 오른쪽만 탐색한다

6

7

10

10

10

5 index ~ 9 index 범위 → (5+9)÷2=7 → 중간값 index 7의 숫자 10은 10보다 크거나 같다 → index7을 포함한 왼쪽을 탐색한다

6

7

10

5 index ~ 7 index 범위 → (5+7)÷2=6 → 중간값 index 6의 숫자 7은 10보다 작다 → index 7부터 탐색한다

7

7 index = 7 index → 두 값이 같아지므로 10의 lower bound의 index는 7이다.

upper bound

숫자 N을 찾을 때, N보다 큰 값이 시작하는 index이다.

위 정렬된 수들에서 10 10 10이 있는데 맨 오른쪽 10이 upper bound가 아님에 주의한다.

맨 오른쪽에 끝값을 배정한다. index=10

배열의 끝 값은 10이므로 10 ÷ 2 = 5 index에서 시작한다. 

-10

-10

2

3

3

6

7

10

10

10

끝값

0~10 index 범위 → 중간값 index 5의 숫자 6은 10보다 작다 → index 5의 오른쪽만 탐색한다

6 index ~ 10 index 범위 → (6+10)÷2=8 → 중간값 index 8의 숫자 10은 10보다 작거나 같다 → index8의 오른쪽을 탐색한다

9 index ~ 10 index 범위 → (9+10)÷2=9 → 중간값 index 9의 숫자 10는 10보다 작거나 같다 → index 10부터 탐색한다

10 index = 10 index → 두 값이 같아지므로 10의 upper bound의 index는 10이다.

중복된 N의 개수 = upper bound - lower bound

import java.io.*;
import java.util.*;
public class Main {
	static int[] arr;
	static int lowerBound(int K) {
		int min=0, max=arr.length;
		while(min<max) {
			int mid = (min+max)/2;
			if(K<=arr[mid]) {
            //하한을 구하기 때문에 같은 값에서도 왼쪽값을 찾아야하므로 부등호 포함
				max=mid;
			}else {
				min=mid+1;
			}
		}
		return min;
	}
	static int upperBound(int K) {
		int min=0, max=arr.length;
		while(min<max) {
			int mid = (min+max)/2;
			if(K<arr[mid]) {
            //상한을 구하기 때문에 값이 같다면 그 보다 큰 값을 탐색해야한다 = 부등호X
				max=mid;
			}else {
				min=mid+1;
			}
		}
		return min;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		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()," ");
		for(int i=0;i<M;i++) {
			int K = Integer.parseInt(st.nextToken());
			int cal = upperBound(K)-lowerBound(K);
			sb.append(cal+" ");
		}
		System.out.print(sb.toString());
}}

카운팅배열보다 메모리에서 유리합니다