[상한과 하한] 숫자카드 2(boj.kr/10816)

숫자카드 2(boj.kr/10816)

 

풀이코드 (상한과 하한 직접 구해보기)

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
using namespace std;
// 10815 숫자 카드

int main(){
	int n, m;
	
	scanf("%d", &n);
	
	vector<int> num(n);
	for(int i = 0; i < n; i++) scanf("%d", &num[i]);
	
	sort(num.begin(), num.begin() + n);
	
	scanf("%d", &m);
	
	for(int i = 0; i < m; i++){
		int x;
		scanf("%d", &x);
		
		int left = 0;
		int right = n - 1;
		bool flag = false;
		
		int lowerBound = 0;
		while(left <= right){
			int mid = (left + right) / 2;
			
			// lowerBound 찾기 (하한)
			if(num[mid] == x){
				flag = true;
				lowerBound = mid;
				right = mid - 1;
			}
			
			else if(num[mid] < x){
				left = mid + 1;
			}
			else{
				right = mid - 1;
			}
		}
		
		left = 0;
		right = n - 1;
		
		int upperBound = n - 1;
		while(left <= right){
			int mid = (left + right) / 2;
			
			// upperBound 찾기 (상한)
			if(num[mid] == x){
				flag = true;
				upperBound = mid + 1;
				left = mid + 1;
			}
			
			else if(num[mid] < x){
				left = mid + 1;
			}
			else{
				right = mid - 1;
			}
		}
		
		if(flag) printf("%d ", upperBound - lowerBound);
		else{
			printf("%d ", 0);
		}
	}
	printf("\n");
}

 

풀이코드 (상한과 하한 라이브러리)

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int main() {
    int n;
    scanf("%d",&n);

    vector<int> a(n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    
    sort(a.begin(), a.end());

    int m;
    scanf("%d",&m);

    for (int i=0; i<m; i++) {
        int number;
        scanf("%d",&number);
        auto l = lower_bound(a.begin(), a.end(), number);
        auto r = upper_bound(a.begin(), a.end(), number);
        printf("%d ",r-l);
    }

    printf("\n");
    return 0;
}

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int main() {
    int n;
    scanf("%d",&n);

    vector<int> a(n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    
    sort(a.begin(), a.end());

    int m;
    scanf("%d",&m);

    for (int i=0; i<m; i++) {
        int number;
        scanf("%d",&number);
        auto p = equal_range(a.begin(), a.end(), number);
        printf("%d ",p.second - p.first);
    }

    printf("\n");
    return 0;
}

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 상한과 하한을 구한다.

- 상한 : 큰 수 중 첫번째 수

- 하한 : 크거나 같은 수 중 첫번째 수

2. 상한과 하한을 뺀다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 주의해야 할 경우는, 수가 존재하지 않을 때이다.

- 수가 존재하는 경우 (flag 가 true 가 되면) 상한과 하한을 찾은 것이기에 둘의 차를 구하면 된다.

- 수가 존재하지 않는다면( flag 가 false 가 되면 ) 0을 출력

2. 하지만, 이것은 엄밀히 따지면, 상한과 하한을 구한 것은 아니다.

- 상한과 하한의 차가 수의 개수이다. 라는 정의를 만족시키려면

- 수가 없을 때, 상한은 마지막 루프에서의 mid 이 될 것이고

하한은 마지막 루프에서의 mid 가 될 것이다.