글 읽기 - 왜 시간초과가 뜨는지 모르겠습니다.

chj4535 5년 전 0

NCard : N개의 수를 퀵소트해준 배열

NNoDuple : NCard에서 중복제거(갯수 추가로)

퀴소트로 NCard 만들고 NNoDuple 로 각 숫자 갯수 세어준뒤에

NNoDuple에서 이분검색을 통해서 각 숫자의 갯수를 출력해줬는데 바로 시간초과가 뜹니다.

NNoDuple도 최대 500,000번인 것 같은데 어디가 문제일까요?

import sys
import random

N = int(input())

NCard = list(map(int,sys.stdin.readline().split(' ')))
NNoDuple=[[0,0] for i in range(N)]

M = int(input())

MCard = list(map(int,sys.stdin.readline().split(' ')))
MRecord=[0]*M

#print(NCard)
#print(MCard)

def Quicksort(Array,Start,End):
    if Start >= End:
        return

    i,j = Start,End
    pivot = Array[random.randint(Start,End)]

    while i <= j:
        while Array[i] < pivot: i+=1
        while Array[j] > pivot: j -= 1
        if i<=j:
            Array[i], Array[j] = Array[j], Array[i]
            i=i+1
            j=j-1
    Quicksort(Array,Start,j)
    Quicksort(Array, i, End)

Quicksort(NCard,0,N-1)

#print(NCard)
NNoDupleNum=0
NNoDuple[0][0]=NCard[0]
NNoDuple[0][1]=1
for i in range(1,N):
    if NNoDuple[NNoDupleNum][0]==NCard[i]:
        NNoDuple[NNoDupleNum][1]+=1
    else:
        NNoDupleNum+=1
        NNoDuple[NNoDupleNum][0] = NCard[i]
        NNoDuple[NNoDupleNum][1] = 1

#print(NNoDupleNum)
#print(NNoDuple)

def BindSearch(Array,front,end,find):
    middle = (front+end)//2
    if front>end or front>end:
        return 0
    if Array[middle][0]==find:
        return NNoDuple[middle][1]
    elif Array[middle][0]>find:
        return BindSearch(Array,front,middle-1,find)
    else:
        return BindSearch(Array, middle+1, end,find)

for i in range(M):
    MRecord[i]=BindSearch(NNoDuple,0,NNoDupleNum,MCard[i])

#print(MRecord)

Ans=''
for i in range(M):
    if MRecord[i]==0:
        Ans += "0 "
    else:
        Ans += str(MRecord[i])+" "

print(Ans[:-1])

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

문제

문제

출처

ICPC

왜 시간초과가 뜨는지 모르겠습니다.

chj4535 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말