예를 들어 길이가 N이고 정수로 이루어진 배열에서 M개의 숫자 유무를 확인해야 한다고 가정해봅시다. 문제 조건에서 N은 최대 10,000, M은 최대 100,000으로 주어졌다고 합시다. 하나의 숫자를 검사할 때마다 배열을 전부 순회한다면 M개의 숫자에서 각각 N번의 검사를 해야 하므로 시간 복잡도는 O(NM)이 됩니다.
문제 조건에 따라 N과 M의 최댓값을 대입하면 10억이라는 결과가 나옵니다. 이는 1억이 훨씬 넘는 수치이므로 코드를 작성하기 전에 더 효율적인 방법을 찾아야 한다는 것을 알 수 있습니다. 이처럼 시간 복잡도를 활용하면 코드를 작성하기 전에 해당 풀이를 검증할 수 있습니다.
잠깐만요
이 문제는 ‘8장 이진 탐색’을 이용하면 O((N+M)logN)의 시간 복잡도로 해결할 수 있으며, HashSet 자료 구조를 이용하면 O(N+M)의 시간 복잡도로 해결할 수 있습니다.