글 읽기 - 시간초과 이유가 궁금합니다.

iwtbakgj 2년 전 0

질문글에서 영감을 얻어 우선 이진탐색으로 타켓번호를 찾고 그 번호의 왼쪽과 오른쪽으로 탐색을 보내 찾아 봤지만 시간초과가 납니다. 한수 가르쳐 주시면 감사하겠습니다.

import sys
def rightcrab(x,array,target):
    cnt=0
    if x==len(array)-1:
        return 0
    x+=1
    while True:
        if target!=array[x]:
            break
        else:
            cnt+=1
            if x==len(array)-1:
                break
            x+=1
    return cnt

def leftcrab(x,array,target):
    cnt=0
    if x==0:
        return 0
    x-=1
    while True:
        if target!=array[x]:
            break
        else:
            cnt+=1
            if x==0:
                break
            x-=1
    return cnt


def chat(start,end,target,array):
    cnt=0
    while start<=end:
        mid=(start+end)//2
        if target==array[mid]:
            cnt=1
            break
        elif target>array[mid]:
            start=mid+1
        else:
            end=mid-1
    return cnt,mid

a=int(sys.stdin.readline())
m=list(map(int,sys.stdin.readline().split()))
b=int(sys.stdin.readline())
n=list(map(int,sys.stdin.readline().split()))
m.sort()
for i in n:
    cnt,T=chat(0,len(m)-1,i,m)
    print(cnt+rightcrab(T,m,i)+leftcrab(T,m,i),end=' ')

fblood53 2년 전 0

카운팅 소트로 풀어보세요

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

문제

문제

출처

ICPC

시간초과 이유가 궁금합니다.

iwtbakgj 2년 전 0

fblood53 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말