백준 10816번 C++ & upper_bound, lower_bound

 

https://www.acmicpc.net/status?user_id=jjune0461&problem_id=10816&from_mine=1 

채점 현황

이번 문제는 처음에 그냥 생각나는 가장 쉬운 방법은 프루트포스로 시작을 했습니다.

솔직히 난이도에 맞지 않는 것은 확실하지만 그냥 해보았고 역시나 시간초과가 발생했습니다.

 

그 다음에 생각을 한 방법은 이진 탐색이었습니다.

이진탐색으로 하려고 생각을 하다가 만약에 상황이 다음과 같다고 가정을 해봅시다.

1

2

3

3

3

3

3

3

4

5

이렇게 되어있다면 같고 싶은 값이 3이라고 했을 때

이진 탐색을 통해서 3을 찾는다면 중앙값이 3인데 앞, 뒤로 얼만큼 더 가야하는지 코딩하기가 너무 어려울 것 같다는

생각을 하게되었습니다.

 

다양한 방식으로 생각을 해보다가 결국 인터넷에 찾아보게 되었습니다.

제가 모르는 algorithm헤더에 존재하는 upper_bound, lower_bound를 발견했습니다.

 

Upper_bound & Lower_bound

간단하게 설명드리겠습니다.

upper_bound: 찾고 싶은 값을 초과하는 값이 처음 나오는 인덱스의 주소값 (<)

lower_bound: 찾고 싶은 값 이상의 값이 처음 나오는 인덱스의 주소값 (<=)

그렇다면 다시 저 배열을 예시로 들어보겠습니다.

1

2

3

3

3

3

3

3

4

5

여기서 3을 초과하는 인덱스가 몇번째 인덱스인지 알고 싶다면 아래처럼 해줘야한다.

lower_bound(a.begin(), a.end(), positions[i]) - a.begin()

lower_bound가 주소값이 나오게 되서

초과하는 값을 처음 찾은 주소 - 1번 인덱스의 주소 를 한다면 몇번째에 있는지 나오게 된다.

 

다른 예시로 여기서 찾고 싶은 값이 3이라고 합시다. 그리고 3이 총 몇번이나 있는지 구하고 싶습니다.

그렇다면 다음과 같이 작성하면 됩니다.

(위 값들은 vector container안에 선언이 되어있으며 vector의 이름은 a입니다.)

cout << upper_bound(a.begin(), a.end(), 3) - lower_bound(a.begin(), a.end(), 3) << endl;

초과하는 인덱스가 처음 나오는 곳은  4가 존재하는 '8'입니다.

이상인 인덱스가 처음 나오는 곳은 3이 처음 존재하는 '2'입니다.

 

이러한 생각을 잡으면 다른 방식의 문제도 쉽게 풀 수 있습니다.

예시를 들어보자면 

"3이상 8미만의 수가 몇번 나오나요?" 와 같은 문제를 예시로 들 수 있습니다.

 

아직 제가 공부하지 못한것은 lower_bound & upper_bound의 return값을 명확하게 모르겠었습니다.

그래서 auto를 쓸까? 아니면 그냥 count에 출력을 할까 생각을 해보았는데 cout에서 계산(-)이 잘 되어서 출력이 되는 것을 보고 출력을 하는 방식으로 선택했습니다.

 

문제 풀이 코드

#include <iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N, M;

int main(int argc, const char* argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;      //N은 상근이가 가지고 있는 숫자 카드의 개수, M은 숫자 카드의 종류 갯수
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    cin >> M;           //M만큼 받아옴
    for (int i = 0; i < M; i++) {
        int number;
        cin >> number;
        //int l = lower_bound(a.begin(), a.end(), number);
        //int u = upper_bound(a.begin(), a.end(), number);
        cout << upper_bound(a.begin(), a.end(), number) - lower_bound(a.begin(), a.end(), number) << " ";
    }
}