파이썬 LASER 문제 메모리 초과

  • riceluxs1t
    riceluxs1t

    안녕하세요
    간간히 외박나와서 문제를 풀고있는 일인 입니다..
    https://svn.algospot.com/judge/problem/read/LASER
    문제 풀고 있는데요, 아래와 같이 접근한 상태입니다.

    점들 N개에 대해서 N Choose 2개의 점쌍에 대해 선을 만들어보고 그게 10 개를 초과하면 답으로 간주하는데요.
    이상하게...python으로 짰는데 처음뜨는 메모리 리밋 초과가 뜨네요.
    정확하게는
    " RTE (SIGKILL: program was forcefully killed, probably memory limit exceeded) "
    와 같은 에러가 뜨는데요. 도대체 파이썬에서 어떤 부분이 메모리를 많이 잡아먹고 있는지 잘 모르겠습니다. dictionary 사용 여부때문인가요? ㅜ 지금 현재 running time은 O(n^2 * dictionaryLookUpTime) 이런 것 같은데 혹시 dictionary같은 hash table을 사용하지 않고 10번 이상 선이 나타나는지를 체크할 수 있는 방법 있다면.. 귓뜸 부탁드립니다.

    아래는 제 코드입니다.

    from itertools import combinations

def makeLine(pointOne, pointTwo):
    #vertical line
    if abs(pointOne[0] - pointTwo[0]) == 0:
        ratio = float('inf')
        intercept = pointOne[0]
    elif abs(pointOne[1] - pointTwo[1]) == 0: 
        ratio = 0
        intercept = pointOne[1]
    else:   
        ratio = abs(float(pointOne[1]) - pointTwo[1])/abs(float(pointOne[0]) - pointTwo[0])
        intercept = pointOne[1] - ratio*pointOne[0]
    return ratio, intercept

def solve(points):

    curCount = {}
    ans = 0

    for pair in combinations(points, 2):
        line = makeLine(pair[0], pair[1])
        if line not in curCount: curCount[line] = 0
        curCount[line] += 1
        if curCount[line] == 10: ans += 1
    return ans

for _ in range(input()):
    inp = []
    for _ in range(input()):
        line = map(int, raw_input().split(' '))
        inp.append(line)
    print solve(inp)


    10년 전
0개의 댓글이 있습니다.

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