포켓몬이 최대 10만개, 질문이 최대 10만개일때

연산이 제일 많이 필요한 케이스는 10만개의 질문이 모두 맨 뒤에 있는 포켓몬의 이름인 경우겠죠 (반복문에 break가 안걸리니까요)

그럼 이때 필요한 대충의 연산 횟수를 계산해 보면

10만 * 10만 * 20(글자수)가 되겠네요. 대략 2천억번의 연산이 필요하네요. 요런 알고리즘 문제 푸실때는 1억번의 연산이 1초 걸린다고 생각하시면 됩니다.

즉 현재 푸신 방식으로는 최악의 경우에 2천 초가 걸리므로 시간초과가 나온겁니다.

이를 해결하는 방법은 매 질문마다 빠르게 찾으면 되겠죠?

그 방법은 이분 탐색에 대해 공부해 보시면 도움이 될 것 같습니다

감사합니다.

궁금한게 있습니다.

정렬된 데이터의 경우에는 이분 탐색으로 범위를 정해서 고를 수 있다고 이해 했습니다.

근데, 포켓몬 도감의 이름의 경우 ABC순서로 정렬된 데이터가 아니기에 

이분 탐색으로 반 찾고 반 찾으면 결국 시간은 똑같은 것 아닌가요?

아니면 제가 뭔가를 잘못 이해하고 있는건가요?

정렬하고 이분 탐색 쓰시면 되죠

정렬을 하면 A로 시작하는 멀리 있는 포켓몬이 앞으로 올텐데 번호를 매길수가 없지 않나요..?

저라면 번호 순으로 정렬된 배열, 사전 순으로 정렬된 배열을 따로 만들겠네요

팁 감사합니다.