파이썬으로 푸는 MEASUREMENT

  • handrake
    handrake 
    import bisect

def insort2(a):
    b = sorted(a)
    count = 0
    nl = []
    for i in range(len(a)):
        j = bisect.bisect_left(b, a[i])
        count += j - bisect.bisect_left(nl, j)
        bisect.insort_left(nl, j)
    return count

for case in range(input()):
    n = input()
    a = [int(x) for x in raw_input().split()]
    print insort2(a)

    안녕하세요. 얼마 전에 가입한 handrake입니다. 다름이 아니라 이 문제에서 핵심은 정렬된 배열에서 원소를 찾을 때 바이너리 서치를 이용하는 것이라고 생각하고 위와 같이 bisect를 이용해 소스를 짰습니다만 시간초과가 나옵니다. 혹시 몰라서 입력 범위에 해당하는 테스트 케이스를 직접 생성해 돌려보니 7초대가 나와 루프에서 다 지우고

        for i in range(len(a)):
        j = 1

    이렇게만 했는데도 1.7초대입니다. 입출력 시간의 문제인가 싶어 raw_input() 대신 sys.stdin.readline()을 써봤는데 별 차이 없는 것으로 봐서 파이썬으로 시간제한 내에 답을 내기는 조금 힘든 것이 아닌가 합니다.

    테스트 케이스를 만든 코드는

    import random

c = 50

print c

for i in range(c):
    n = random.randint(1, 50000)
    print n
    print ' '.join([str(random.randint(1, 1000000)) for x in range(n)])

    입니다.


    10년 전
1개의 댓글이 있습니다.
  • Being
    Being

    입력이 워낙 커서 다른 언어도 상황은 마찬가지인데, 여기에 시간을 더 주는 경우 "C로 짠 시간 복잡도가 느린 알고리즘"이 통과할 우려가 있어서 간단하지 않은 문제입니다. 특정 언어에만 시간을 더 주는 것도 가능한 한 방법이겠습니다만 문제마다 그걸 임의로 지정하는 것도 쉽지가 않구요(이런 문제가 이것만 있는 것도 아니니까요...)


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.