인프런 커뮤니티 질문&답변

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

6-D

6-D lower_bound 질문있습니다 :)

해결된 질문

작성

·

24

0

안녕하세요 선생님 🙂

lower_bound와 관련하여 궁금한 것이 있어서 질문드립니다.

해당 문제는 lower_bound를 이용하여 A 안에 있는 요소들 중 하나를 골라서 B에 있는 요소보다 큰 경우를 누적하여 더한 후에 출력하는 문제였습니다.

문제의 결과 값에서 lower_bound의 역할을 유추해보면, 1, 2번째 파라미터에 넣는 배열의 범위에서 3번째 파라미터에 있는 요소보다 작은 요소의 개수를 출력해주는 함수라는 것을 알 수 있었습니다.

반대로 upper_bound는 작은 요소가 아닌 큰 요소의 개수를 출력해주는 함수라는 것을 알게 되었습니다.

그렇다면, 같은 요소의 개수를 출력해주는 방법도 있을 거라고 생각하는데요, 구글을 아무리 뒤져봐도 키워드 선택을 잘못해서 그러는건지.. 관련 자료를 찾을 수 없었습니다. 혹시 이런 함수가 따로 있다면 알려주시면 도움이 많이 될 것 같습니다 :)

lower_bound가 같은 경우도 처리해준다는 자료를 보긴 했는데요, 이 자료에 신뢰성이 있으려면 해당 문제에서 A와 B의 요소가 같아도 A가 B를 잡아먹을 수 있다는 조건을 만족해야 할 것 같습니다. 아래는 제가 보았던 자료의 링크입니다.

https://chanhuiseok.github.io/posts/algo-55/

c++코딩-테스트

답변 1

1

지식공유자

안녕하세요 유태님 ㅎㅎ

같은 요소의 개수를 출력해주는 방법

->

lower_bound와 upper_bound를 응용하시면 됩니다.

이렇게 하시면 됩니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;  
int t, n, m; 
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL); 
    vector<int> a = {1, 2, 2, 2, 3};
    auto i = lower_bound(a.begin(), a.end(), 2);
    auto i2 = upper_bound(a.begin(), a.end(), 2);
    cout << (int)(i2 - i) << "\n"; 
}

감사합니다.

작성한 질문수