시간 복잡도라는 개념을 정확히 이해하셔야 합니다.

위 알고리즘의 경우는 M개 각각의 숫자를 최대 N번 비교하게 되므로, 최대 NM = 10^5 * 10^5 = 10^10번의 비교 연산을 수행하게 됩니다.

이것을 위 알고리즘이 O(NM)의 시간복잡도를 가지고 있다고 이야기합니다.

일반적으로 채점 서버에서 프로그램이 1초 동안 수행할 수 있는 연산의 횟수는 10^8~9 정도입니다. 따라서 위 알고리즘을 실행하는 데 약 10~100초 정도의 시간이 걸리게 됩니다.

이것은 문제에서 요구한 프로그램의 수행 시간보다 길므로 시간 초과가 발생할 것입니다.

위 문제는 O(NM)보다 더 짧은, O((M+N) logN)의 시간 복잡도로 해결할 수 있습니다.

비교 연산을 NM번보다 적게 수행하는 알고리즘을 생각해야 하겠죠?

소스 보기는 문제를 풀어야 볼 수 있습니다.

뭘 풀어도 시간 초과가 나는 것은 문제 풀이를 처음 시작할 때 흔히 겪는 상황인데, 효율적인 알고리즘을 이용해서 문제를 풀지 않았기 때문입니다.

예를 들어, 이 문제의 경우에는 이분 탐색을 사용해서 풀어야 합니다. 아마도 시간 초과가 나는 이유는 각각의 숫자를 찾을 때마다 전체 숫자에서 숫자를 하나씩 찾아서일텐데, 이 방법은 어떤 방법을 사용해도 시간 초과를 받게 됩니다.

창의적인 방법을 새로 생각해낼 필요는 없고, 이미 존재하는 알고리즘을 공부해서 문제를 풀면 됩니다.

알고리즘 문제해결전략 책 추천합니다.

http://book.algospot.com/