wccho89   4년 전

cin을 쓰면 시간초과된다고 하여 모두 scanf랑 printf로 바꿨는데도..

시간초과가 계속 뜨네요...

이유를 모르겠습니다 ㅠㅠ

sgchoi5   4년 전

1) cin 을 쓰면 안 된다

=> 요거 한 번 읽어 보세요. http://gooddaytocode.blogspot....

cin/cout 는 입출력 회수가 작은 경우에 써도 됩니다. 입출력 회수가 많아지면 문제인 것 이고요.

2) 이분탐색은 입력값이 정렬이 되어야 하는데, 이 정렬 방법이 문제네요

이분탐색의 복잡도는 O(logN) 인데, 정렬 방식이 O(N2) 이네요. 

정렬 방식을 quick sort 나 merge sort 같은 O(NlogN) 시간복잡도를 가진

알고리즘으로 변경하셔야 합니다.

이분탐색: O(logN) 에서 N 이 500,000 이면 대략 18

정렬1: O(N2) 500,000 * 500,000 = 250,000,000,000 = 2천5백억이네요.

정렬2: O(NlogN) 500,000 * 10 = 9,000,000 = 9 백만이네요.

3) 공간 복잡도를 생각하면 이 문제는 정렬 안 해도 됩니다.

입력값의 모든 범위인 2 천만개 숫자를 의 int array 를 잡으면 76MB 면 됩니다. bool 로 하면 1/4 이겠네요.

wccho89   4년 전

좋은 답변 감사합니다 ^^

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