[python] Codility Lesson 6-4. NumberOfDiscIntersections

 

1. Sorting section에 위치한 문제라 sort를 해야 시간복잡도에서 무사히 통과하리라 생각했지만 쉽게 방법이 떠오르지 않아 손 내키는데로 작성해 보았다.

 

원의 중심은 list에서 순차적으로 증가하니, 2중 for문을 돌면서 first_비교원의 최대값이 second_비교원의 최소값보다 크거나 같은경우 answer_count += 1

 

정확도는 100%를 달성했지만 performance에서 망가진 O(N*2) 코딜리티는 N*2을 가만두지 않는다 ㅠㅠ

 

 

def solution(A):
    answer_count = 0

    for i in range(len(A)-1):
        for j in range(i+1, len(A)):
            if i+A[i] >= j-A[j]:
                answer_count +=1

    if answer_count > 10000000:
        answer_count = -1
    return answer_count

 

 

2. 깔끔한 정답을 찾아 보았다.

 

정말 대단하다, 어떻게 이런 생각을 할 수 있을까 같은 사람이 ㅠㅠ

 

1. 가장 최소범위를 지나는 원을 시작으로 포함되는 원을 만날때 마다 r += 1, 그리고 t += 1

 

2. for 문을 돌면서 d[1] == 1, 즉 원이 하나 완성된 것을 만나면 t -= 1

def solution(A):
    disc = []
    for i, v in enumerate(A):
        disc.append((i-v, -1))
        disc.append((i+v, 1))

    disc = sorted(disc)
    t = 0
    r = 0

    for d in disc:
        if d[1] == 1:
            t -= 1
        else :
            r += t
            t += 1
    
    return r if r <= 10000000 else -1