cardbt   4년 전

안녕하세요.


숫자 카드 2 문제를 해결하기 위해, 퀵정렬과 이분 탐색을 이용해서 풀었습니다.

두 개의 알고리즘 처리 시간을 생각해보면, 제한 시간내에 처리가 가능할 것으로 보이는데, 시간초과로 합격하지 못했습니다.


예상컨데 최악의 경우인 50만, 50만건일때 INPUT을 받는 시간이 너무 오래 걸리는게 아닌가 생각됩니다.

scanf를 이용하여 숫자형태(long형)로 INPUT을 받았는데 도합 100만건에 대한 INPUT을 받게 되면 2초내에 알고리즘이 완료되기 어려워 보이는데요.


이 부분을 어떻게 해결하셨는지 궁금합니다.

gets나 문자열로 받아서 strtok로 처리하려면,  받는 문자열이 최악의 경우에 50만 *  9(-10000000)로 매우 큰 메모리가 필요하게 되는데요.


다른 좋은 방법이 있을까요?

3587jjh   4년 전

scanf로도 됩니다

cardbt   4년 전

흠..

그럼 단순하게 퀵정렬과 이분 탐색만으로 해결되는 문제가 아닌가 보군요.

어려운 문제였네요 ㅎㅎ


답변 감사합니다

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