BOJ - 10816 숫자 카드 2

leehyunjon·2022년 5월 26일

boj lower bound upper bound 이분 탐색

Algorithm

목록 보기

47/162

10816 숫자 카드 2 : https://www.acmicpc.net/problem/10816

Problem

Solve

이전에 풀었던 문제 에서는 배열에 target의 존재 여부를 확인한 문제였다면. 이번 문제는 배열에 존재 여부가 아닌 존재하는 개수를 구하는 문제이다.

이진 탐색과 비슷하지만 조금 변형된 방법인 Upper Bound와 Lower Bound를 사용한다.
Lower Bound는 배열에 존재하는 target에서 최초의 값을 반환하고 Upper Bound는 배열에 존재하는 target보다 다음으로 큰 최초의 값을 반환하는 것이다.
그렇기 때문에 Upper Bound에서 반환된 값 - Lower Bound에서 반환된 값은 배열에 존재하는 target의 개수가 되게 된다.
만약 배열에 target이 존재하지 않는다면 Upper Bound - Lower Bound는 0이 되게 된다.

그리고 조심해야할 것은 Lower와 Upper에서 end포인터는 N-1이 아닌 N이어야한다. 그렇지 않으면 target의 개수가 1개가 누락되는 경우가 생긴다.
예를 들어 {1,2,2,2}에서 target=2를 찾을 때 Lower에서 1이, Upper에서 3이 반환되어 2가 되어버린다.

Lower Bound

static int lowerBound(int num){
		int start=0;
		int end=N;

		//start와 end가 겹치지 않는 동안 반복한다.
		while(start<end){
			int mid = (start+end)/2;

			//범위 안에 target을 넣기 위해 임의의 값(arr[mid])가 크거나 같을 때 end를 mid로 갱신한다.
			if(arr[mid] >= num){
				end = mid;
			}else{
            //마찬가지로 target을 범위 안에 넣기 위해 임의의 값이 target보다 작다면 target보다 작은 값은 범위에서 제외하기 위해 start에 mid+1을 갱신.
				start = mid+1;
			}
		}

		//배열에 target이 있다면 start와 end가 겹쳤을때의 end가 target의 위치이다.
        //배열에 target이 존재하지 않다면 target보다 다음으로 큰 값의 첫번째 위치이다.
		return end;
	}

Upper Bound

static int upperBound(int num){
		int start=0;
		int end=N;

		while(start<end){
			int mid = (start+end)/2;

			//Lower Bound와 다른점
            //arr[mid]가 target보다 클 때 mid 왼쪽 범위로 줄인다.
			if(arr[mid]>num){
				end = mid;
			}else{
            //arr[mid]가 target보다 작거나 같을 때 mid의 오른쪽 범위로 줄여서 target보다 큰 값을 범위안에 포함시켜야한다.
				start = mid+1;
			}
		}

		return end;
	}

자세한 설명이나 그림으로 이해하려면 바킹독님 블로그에서 보면 쉽게 이해할수 있다.

Code

public class 숫자카드2 {
	static int N;
	static int M;
	static int[] arr;
	static int[] arr2;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		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());
		}
		M = Integer.parseInt(br.readLine());
        //비교 배열
		arr2 = new int[M];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<M;i++){
			arr2[i] = Integer.parseInt(st.nextToken());
		}

		//기준 배열 오름차순 정렬
		Arrays.sort(arr);

		StringBuilder sb = new StringBuilder();
		for(int num : arr2){
        	//target의 최초 index
			int startIdx = lowerCase(num);
            //target의 다음으로 큰 값의 최초 index
			int endIdx = upperCase(num);

			sb.append(endIdx-startIdx).append(" ");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static int lowerCase(int num){
		int start=0;
		int end=N;

		while(start<end){
			int mid = (start+end)/2;

			if(arr[mid] >= num){
				end = mid;
			}else{
				start = mid+1;
			}
		}

		return end;
	}

	static int upperCase(int num){
		int start=0;
		int end=N;

		while(start<end){
			int mid = (start+end)/2;

			if(arr[mid]>num){
				end = mid;
			}else{
				start = mid+1;
			}
		}

		return end;
	}
}