태그:
주어진 카드 덱에 주어진 숫자들이 몇 개 존재하는지 출력하는 문제입니다. 먼저 O(n log n)의 시간복잡도로 카드 덱을 정렬한 후, 각 숫자들에 대해 이분 탐색으로 인덱스를 찾습니다. 여기서 인덱스를 찾을 때에는 두 개의 인덱스를 찾아야 합니다. 그 이유는 중복이 가능하기 때문에 같은 숫자가 여러 개 존재할 수 있고, 같은 숫자가 존재하는 범위를 구하기 위해서입니다. 따라서 해당 인덱스에는 원하는 값이 있고 그 이전 원소의 값은 원하는 값이 아닌 것을 시작 인덱스, 반대로 그 다음 원소의 값이 원하는 값이 아닌 것을 끝 인덱스로 잡아서 두 인덱스의 차이+1을 구하면 카드에 존재하는 숫자의 개수가 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2020-03-31 01:06:38 |