백준 10816. 숫자 카드 2 [실패]

1.실패 원인

원인은 두 가지이다. 가장 큰 문제는 찾으려는 배열의 중복 요소의 개수를 출력하는 문제에서 lower_bound, upper_bound 함수를 사용해야 하는데, 이를 알지 못해서이다. 물론 아이디어가 있었다면 직접 구현이라도 했을텐데 거기까지 미치지 못했다. 두 번 째는 역시나 이분 탐색을 정확히 이해하지 못해서인듯 하다. 이분 탐색은 간단하다. 범위를 배열의 처음과 끝으로 설정하고 인덱스를 반으로 나누며 정렬된 배열(찾으려는 값이 들어있는 배열)과 크기를 비교하여 찾는 값의 범위를 줄여나가는 방식이다. 정말 별것 없는데 막상 써먹으려니 잘 생각이 안난다.

 

2.작성 코드

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        vector<int> v(N);

        for (int i = 0; i < N; i++)

                 cin >> v[i];

 

        sort(v.begin(), v.end());

        int M;

        cin >> M;

 

        for (int i = 0; i < M; i++)

        {

                 int num;

                 cin >> num;

 

                 cout << upper_bound(v.begin(), v.end(), num) - lower_bound(v.begin(), v.end(), num) << " ";

        }

        cout << "\n";

        return 0;

}



//출처: https://jaimemin.tistory.com/993 [꾸준함]

3.참고 코드

https://jaimemin.tistory.com/993

백준 10816번 숫자 카드 2

4. 해결 방안

그나마 위로가 되는건 몰랐던 함수의 존재를 알게 됐다는 점이다. 처음엔 같은 인덱스에 대해 카운트 정보를 저장해야 한다고 생각해서 map을 사용했었는데, upper_bound , lower_bound의 차이를 통해서 이분 탐색 + 같은 요소의 개수 효과까지 낼 수 있다는 것을 처음으로 알게 됐다.

 

그리고, vector의 초기 size 설정을 vector<int> v(N) 이런 식으로 할 수 있다는 것도 처음 알았다.. 굉장히 부끄러운 점이기도 하지만 배열과 달리 size 설정 함수들을 사용해도 원하는 개수만큼 벡터가 늘어나지 않았었는데, 위의 방식으로 vector 값을 설정할 수 있다는 것도 꾸준함님 덕에 처음 알게 됐다.