10816번 숫자 카드2(lower, upper)

#문제링크 : https://www.acmicpc.net/problem/10816

민수가 N개의 숫자카드를 가지고 있고 영희가 M개의 숫자를 말한다. 영희가 말한 숫자가 민수가 가지고 있는 숫자카드에 존재하면 그 갯수를 반환하고 없으면 0을 반환한다. 우선, 두 배열을 만들고 민수의 배열을 정렬한 후 lower_bound와 upper_bound의 특성을 고려하여 각 숫자카드가 몇개 존재하는지 찾아내었다. 잘 동작하지만, 시간초과가 떴다.

※주의사항

1. lower_bound와 upper_bound의 반환형은 반복자(iter)다.

2. lower_bound와 upper_bound는 이미 정렬되어 있는 배열에 사용가능하다.

3. lower_bound는 찾고자 하는 값 "이상"이 처음으로 나타나는 위치, 즉, 찾고자 하는 값을 포함한다.

4. upper_bound는 찾고자 하는 값보다 "큰" 값이 처음으로 나타나는 위치, 즉, 찾고자 하는 값을 포함하지 않는다. 

5. lower_bound( 찾고자하는 범위의 배열 이름, 배열이름+배열사이즈, 찾으려는 값 )
EX) lower_bound( arr, arr+20, 8 ) -> 크기 20인 arr배열에서 8보다 크거나 같은 값이 시작되는 위치 반환

6. upper_bound( arr, arr+20, 8 ) -> 크기 20인 arr배열에서 8보다 큰 값이 시작되는 위치 반환

1. Code

<2nd try>

위에선 lower_bound와 upper_bound와의 관계를 생각하지 못하고 단순 반복문을 하나 더 넣어, 시간초과가 발생했다.

다음은 수정한 코드다.

※주의사항

1. 정렬된 배열에서 upper_bound - lower_bound의 값으로 키가 몇번 중복되었는지 알 수 있다.

2. Code