qorrhktk66   1년 전

배열이나 리스트를 쓰지 않고는 문제를 풀 수 없을 것 같습니다.

근데 검색 속도는 배열이 리스트보다 빠르다고 알고 있어서 배열을 사용했는데 시간초과가 계속 나네요..

숫자인지 문자인지 구분할 때 쓴 if문은 원래 스위치로 써서 case 0~9, 디폴트로 나눴는데 그때도 시간초과가 떳구요.

qwer9412   1년 전

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

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


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

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

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

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

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

qorrhktk66   1년 전

감사합니다.

qorrhktk66   1년 전

궁금한게 있습니다.

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

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

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

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

ehdrmsl2001   1년 전

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

qorrhktk66   1년 전

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

ehdrmsl2001   1년 전

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

qorrhktk66   1년 전

팁 감사합니다.

댓글을 작성하려면 로그인해야 합니다.