다양한 방법이 있겠지만 저는 정렬, 이진 탐색으로 해결했어요

입력 데이터의 크기에 대한 프로그램의 수행시간 분석이 필요합니다.

일반적으로 1억 번의 기본연산(덧셈, 할당, 비교연산... 등)을 수행하는데 소요되는 시간을 1초로 생각합니다.

예를 들어, 아래의 코드는 제 PC에서 release모드로 0.028초가 나오네요.

작성하신 소스는 최대 10억 개의 숫자를 입력받아 배열 input[]에 저장하고, 또 검색 대상 숫자를 최대 10억 개를 받아서 배열 compare[]에 저장한 뒤,

compare[]에 있는 숫자를 하나씩 차례대로 input[]배열에서 찾아서 존재 여부를 출력하는 것으로 보입니다.

여기서, 이 문제에 대한 최악의 입력에 대한 예시로.

input[]에는 10만 개의 숫자가 모두 3이 입력되고, compare[]에는 10만 개의 숫자가 모두 1이 입력된다고 해봅시다.

찾을 대상 숫자가 1인데 input[]에는 1이 존재하지 않으므로, 프로그램은 input[]배열의 처음부터 끝까지 10만 개의 데이터에 대해 비교연산을 수행하게 됩니다.

그런데, compare[]의 크기도 10만개 이므로, 결론적으로 10만 번의 비교연산을 10만 번 수행하게 됩니다.

간략하게 요약하자면, 각각의 최대 크기가 10만인 변수 limit_compare, limit_input에 대해 반복문을 이중으로 수행하므로

작성하신 소스의 최악의 연산 수는 10만*10만 == 100억 번임을 알 수 있습니다.

결국 문제에서 요구하는 제한시간 이내에는 통과하기 힘든 소스입니다.

혹시 잘 모르겠거나 좀 더 힌트를 얻고 싶으시다면 또 알려드리겠슴니다

화이팅하십셔! 

해슁을 이용하여 문제를 해결할 수도 있습니다.

소스 첨부합니다~

해쉬값을 더 큰 값으로 하면 더 빨라질 줄 알았는데 꼭 그렇지도 않군요.... 1018이 940509보다 빠르다니..