글 읽기 - python 시간초과 질문드립니다.

bfinecpa 2년 전 0

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

우선 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에선 통과합니다.

# --------------  1번 코드 ------------------
import sys
input=sys.stdin.readline
a=int(input())
b=list(map(int,input().split()))
b.sort()
#input()도 마지막 2줄은 생략했습니다.
#이진탐색으로 index를 찾습니다.
def BS(start_idx, end_idx, elm): #매개변수 elm은 찾을 정수입니다.
    while(start_idx<=end_idx):
        mid_idx=(start_idx+end_idx)//2
        if b[mid_idx]==elm:
            return mid_idx
        elif b[mid_idx]>elm:
            end_idx=mid_idx-1
        else:
            start_idx=mid_idx+1
    else:
        return -1
# count_elm함수는 찾은 인덱스로부터 좌,우를 검사하여 갯수를 구합니다.
def count_elm(start_idx,elm): #여기서 elm은 BS로 찾은 인덱스 값입니다.
    global elm_count         
    if start_idx!=-1:
        elm_count+=1
        get_small_idx=start_idx-1
        get_big_idx=start_idx+1
        while 0<=get_small_idx:
            if b[get_small_idx]==elm:
                elm_count+=1
                get_small_idx-=1
            else:
                break
        while get_big_idx<a:
            if b[get_big_idx]==elm:
                elm_count+=1
                get_big_idx+=1
            else:
                break
#출력은 제거했습니다. (for i in d:이용해서 출력했습니다.)
# ------------------ 2번 코드---------------
import sys
input=sys.stdin.readline

a=int(input())
b=list(map(int,input().split()))
c=int(input())
d=list(map(int,input().split()))
b.sort()

def BS(start_idx, end_idx, elm, real_elm): 
    while(start_idx<=end_idx):
        mid_idx=(start_idx+end_idx)//2
        if b[mid_idx]>elm:
            end_idx=mid_idx-1
        else:
            start_idx=mid_idx+1
    return start_idx
    
for i in d:
    print(BS(0,len(b)-1,i+0.5,i)-BS(0,len(b)-1,i-0.5,i), end=' ')

ahmg1216 2년 전 1

두가지 방법이 있습니다

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

이분 탐색을 빨리 해줍니다

2. 20000001의 배열 이용

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

ahmg1216 2년 전 1

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

bfinecpa 2년 전 0

감사합니다

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