태그:
주어진 길이 N의 수열에 특정 수가 존재하는지를 M번 구하는 문제입니다. 먼저 주어진 길이 N의 수열을 O(N log N)의 시간복잡도로 정렬합니다. 그 이후 나중에 주어진 수열의 각 수에 대해 이분 탐색을 이용하여 시간 복잡도 O(log N)로 검색합니다. 이렇게 O((M + N) log N)의 시간복잡도로 답을 구할 수 있습니다.
길이 N의 수열을 정렬하지 않는다면 시간복잡도가 어떻게 되는지 알아봅시다. 어떤 수가 수열에 존재하는지 검색하는 과정은 선형 탐색을 사용할 수 밖에 없습니다. 이 과정은 각 수마다 O(N)의 시간복잡도가 필요한데, 찾으려는 수가 총 M개이므로 총 시간복잡도는 O(MN)이 됩니다. 이렇게 풀면 시간이 부족하여 문제를 맞추지 못하게 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-30 21:47:22 |