글 읽기 - (파이썬) O(log N!) 이라고 생각하는데 시간초과가 납니다.

heyksw0208 2년 전 0

입력을 받을때마다 배열에서 이진탐색을 해서 적절한 위치에 삽입을 해줬습니다.

1. 시간복잡도는 대략 log1 + log2 + log3 + log4 + ... + logN = log N! 이 된다고 생각하는데 맞을까요?

2. 리스트 중간에 insert(idx+1, value) 해주는 것보다 arr = arr[:idx] + [value] + arr[idx:] 가 빠르다고 생각하는데 맞을까요?

만약 제가 O(log N!) 의 알고리즘을 제대로 짠게 맞다면 시간초과가 나지 않았겠죠 ㅠ 도움 부탁드립니다..

import sys
N = int(sys.stdin.readline())
tempArr = []

for _ in range(N):
    x = int(sys.stdin.readline())
    
    if not tempArr:
        tempArr.append(x)
    elif len(tempArr) == 1:
        if tempArr[0] < x:
            tempArr.append(x)
        else:
            tempArr = [x] + tempArr
    else:
        left = 0
        right = len(tempArr) - 1
        answer = 0
        # 이진탐색. answer 보다 한칸 뒤에 넣고 싶음.
        while left <= right:
            mid = (left + right) // 2
            if x < tempArr[mid]:
                right = mid - 1
            elif x > tempArr[mid]:
                left = mid + 1
                answer = mid
            else:
                answer = mid
                break

        idx = answer
        
        # 만약 제일 작은 수 였다면 앞에 넣어줌.
        if idx == 0 and x < tempArr[0]:
            tempArr = [x] + tempArr
        # 일반적인 경우는 idx 뒤에 넣어줌.
        else:
            tempArr = tempArr[:(idx + 1)] + [x] + tempArr[(idx + 1):]
            
    # 중간값 구하기
    if len(tempArr) % 2 == 1:
        print(tempArr[len(tempArr) // 2])
    else:
        one = tempArr[(len(tempArr) // 2) - 1]
        two = tempArr[len(tempArr) // 2]
        print(min(one, two))

lambda 2년 전 1

35,38번째줄에서 temparr 전체를 복사하기 때문에 느립니다. list.insert를 써도 크게 달라지지는 않을 것 입니다. 둘 다 O(n)이고 복사하는 것을 n번 반복하기 때문에 전체 시간 복잡도는 O(logn!)=O(nlogn) 보다는 O(n**2)에 가깝습니다.

리스트가 아닌 다른 자료구조를 이용해 보세요.

heyksw0208 2년 전 0

@lambda

저번에도 도움 주셨던 분이군요..!

덕분에 공부됐습니다. 감사합니다.

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

문제

문제

출처

ICPC

(파이썬) O(log N!) 이라고 생각하는데 시간초과가 납니다.

heyksw0208 2년 전 0

lambda 2년 전 1

heyksw0208 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말