[백준 10816번] 숫자 카드 2 - Upper Bound, Lower Bound

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

값이 정렬된 배열에서 중복된 값이 있을 때, 이분 탐색으로 중복된 영역의 하한, 상한 경계를 찾아낼 수 있으면 쉽게 풀 수 있는 문제입니다.

 

 

lower, upper 두 경우에 범위 설정이 살짝 달라집니다.

lower에서는 왼쪽 범위가 start~mid 가 되고 오른쪽 범위는 mid+1~end가 되지만

upper에서는 왼쪽 범위가 start~mid-1, 오른쪽은 mid~end가 됩니다.

 

위처럼 정의하면 중복된 값이 여러개 있는 경우, 값이 하나만 있는 경우 모두 인덱스를 찾아낼 수 있습니다.

 

...
/*
백준 10816번 - 숫자 카드 2
 */
public class Main {
	static int N,M;
	static int[] cards;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		cards = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			cards[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(cards);
		M = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens()){
			int targetNum = Integer.parseInt(st.nextToken());
			int upper = upperBound(targetNum);
			int lower = lowerBound(targetNum);
			if(upper != lower) {
				sb.append(upper - lower + 1);
			}
			if(upper == lower) {
				if(upper == -1) sb.append(0);
				else sb.append(1);
			}
			sb.append(" ");
		}

		sb.deleteCharAt(sb.length()-1);
		System.out.println(sb.toString());
	}

	private static int lowerBound(int targetNum) {
		int start = 0; int end = cards.length-1;

		while(true) {
			int mid = (start+end)/2;
			int cardNum = cards[mid];

			if(start == end) {
				if(cardNum == targetNum) return start;
				return -1;
			}

			if(cardNum >= targetNum) {
				end = mid; continue;
			}

			if(cardNum < targetNum) {
				start = mid+1; continue;
			}
		}
	}

	private static int upperBound(int targetNum) {
		int start = 0; int end = cards.length-1;

		while(true) {
			int mid = (start+end+1)/2;
			int cardNum = cards[mid];

			if(start == end) {
				if(cardNum == targetNum) return start;
				return -1;
			}

			if(cardNum > targetNum) {
				end = mid-1; continue;
			}
			if(cardNum <= targetNum) {
				start = mid; continue;
			}
		}
	}
}