bfinecpa   11달 전

문제를 이분탐색을 사용하여 코드를 작성했습니다.

우선 M=1일때만 생각했습니다. M은 마지막에 곱하기만 하므로 시간을 줄이는데 있어서 크게 중요하지 않다고 생각했습니다.

1번코드를 보면 인덱스를 찾는데 O(logN)의 시간이 든다고 생각합니다. 찾은 정수의 갯수를 세기위해 선형탐색을 이용했으므로 O(N)의 시간이 든다고 생각합니다. 

그럼 최악의 경우 O(logN)+O(N)이라 생각합니다. ex) N이 하나의 값으로 이뤄진 경우 (1 1 1 1 1 1 1 1 1 1) 찾으려는 값 1

2번코드는  찾으려는 정수에 0.5를 더한 값과 0.5를 뺀 값, 총 두개의 값을 이분탐색으로 구했습니다. 물론 정수가 아니므로 그 값을 찾을 수는 없지만 이분탐색이 끝날 때의 이분탐색 함수의 start 인덱스를 서로 빼주면 찾으려는 수의 갯수가 나옵니다. 여기서 시간복잡도는 두번의 이분탐색이므로 2O(logN)이라 생각합니다.  

1번코드, 2번 코드 모두 시간초과가 납니다. 

파이썬 딕셔너리 사용 말고 이분탐색을 사용해서 시간을 줄일 방법의 힌트를 얻고 싶습니다.

그리고 제가 구한 시간복잡도에서 틀린 점이 있으면 알려주세요.

2번코드는 pypy3에선 통과합니다.

ahmg1216   11달 전

두가지 방법이 있습니다 

1.라이브러리의 bisect모듈 사용 

이분 탐색을 빨리 해줍니다 

2. 20000001의 배열 이용

사실상 딕셔너리 사용과 크게 다르지 않습니다

ahmg1216   11달 전

참고로 1번 코드는 찾는데  O(N) 이고 찾아야 하는건  K개라 할때  O(NK)라 당연히 시간초과가 납니다

bfinecpa   11달 전

감사합니다

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