문제

[백준] 숫자카드 2

접근방법

현재 알고리즘 공부를 바킹독님 강의를 보면서 하고 있는데 이분탐색의 예제문제로 나와서 풀이를 알고 접근한 문제다

문제를 보면 이분탐색의 전형적인 형태이다
STL 에 있는 함수로도 해결할 수 있지만 내부에 돌아가는 원리를 이해하는 것이 중요하고 또 다른 이분탐색 응용문제가 나왔을 때 내부논리를 수정해야 할 수도 있기 때문에 이분탐색을 직접구현하는 방식을 선택했다

sort

이분탐색이 제대로 되려면 배열이 정렬되어 있어야 한다 그래서 첫번째로 sort를 해준다

카드갯수찾기

카드의 갯수는 카드가 처음 등장하는 위치와 마지막 등장하는 위치로 구해줄 수 있다
원래의 이분탐색은 mid가 target값을 찾으면 return하지만 이 문제의 해결법에서는 같을 경우에 탐색영역을 수가 큰 쪽이나 작은 쪽으로 옮겨서 중복되는 값이 나오지 않을 때 멈추게 한다

이 접근방식이 재밌었다 조건을 하나를 추가한 다음, 나머지는 원래의 논리가 그대로 작용되게 한 점이 깔끔했다

결과 차례로 출력

나오는 결과를 새로운 배열에 넣어줄 필요없이 차례로 출력하면 정답이 나온다

해결

#include <bits/stdc++.h>
using namespace std;

int cards[500000];
int targets[500000];

int GetLowerIdx(int targetNum, int len) {
	int st = 0;
	int en = len-1;
	int idx = 0;
	while (st <= en) {
		int mid = (st + en) / 2;
		if		(cards[mid] <  targetNum) { st = mid + 1; }
		else if (cards[mid] >= targetNum) { en = mid - 1; }

		idx = st;
	}
	return idx;
}

int GetUpperIdx(int targetNum, int len) {
	int st = 0;
	int en = len-1;
	int idx = 0;
	while (st <= en) {
		int mid = (st + en) / 2;
		if		(cards[mid] <= targetNum) { st = mid + 1; }
		else if (cards[mid] >  targetNum) { en = mid - 1; }

		idx = st;
	}
	return idx;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int cardCount; cin >> cardCount;

	for (int i = 0; i < cardCount; i++) cin >> cards[i];
	sort(cards, cards + cardCount);

	int targetCount; cin >> targetCount;
	
	for (int i = 0; i < targetCount; i++) cin >> targets[i];

	for (int i = 0; i < targetCount; i++) {
		int result;
		result = GetUpperIdx(targets[i], cardCount) - GetLowerIdx(targets[i], cardCount);
		cout << result << ' ';
	}

}