글 읽기 - 파이썬 시간초과 질문드립니다.

kyi9592 1년 전 0

처음에 list_n.sort()가 시간초과를 야기하는줄알고 quick sort로 바꿔서했는데 똑같이 시간초과가 나서 for문을 돌면서 N의 요소들을 이분탐색으로 진행하는거는 시간복잡도가 NlogN으로 생각했는데 이것보다 더 줄여야하는건가여??

import sys
sys.setrecursionlimit(500000*500)
N = int(input())
list_n = list(map(int, input().split()))
M = int(input())
list_m = list(map(int, input().split())) # target list
count = [0] * (max(list_n)+1)
def quick_sort(list):
    if len(list)<=1:
        return list
    pivot = list[0]
    tail = list[1:]
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x>pivot]
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
list_n = quick_sort(list_n)
def left_search(list,index, target):
    if list[index] == target:
        if index-1>=0:
            tmp = left_search(list, index-1, target)
            return tmp+1
        else:
            return 1
    else:
        return 0
    
def right_search(list, index, target):
    if list[index] == target:
        if index+1<N:
            tmp = right_search(list, index+1, target)
            return tmp+1
        else:
            return 1
    else:
        return 0

def binary_search(list, start, end, target, count):
    while start<=end:
        mid = (start+end)//2
        if list[mid] == target:
            count +=1
            tmp1 = 0
            tmp2 = 0
            if mid - 1>=0:
                tmp1 = left_search(list, mid-1, target)
            if mid + 1 <N:
                tmp2 = right_search(list, mid+1, target)
            return count +tmp1 +tmp2
        elif list[mid]>target:
            end = mid-1
        else:
            start = mid+1
    return 0
for i in range(M):
    print(binary_search(list_n, 0, N-1, list_m[i], 0), end=" ")

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

문제

문제

출처

ICPC

파이썬 시간초과 질문드립니다.

kyi9592 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말