(코딜리티) Lesson 6. [Sorting] : NumberOfDiscIntersections - python

이 문제는 문제자체를 이해하지 못해서 풀지 못하고, 이해하고 난 뒤에는 효율성문제로 결국 풀지 못하였습니다.

intersection을 계속 접점으로만 이해해서.. 왜 11이 return되는 거지 생각했지만, 알고보니 원과 원이 겹쳐지는 것을 의미하더군요.. 

 

그리고 알고리즘은 이해는 했으나, 원리가 어디서 나오는 건지 이해할 수 없어서 제가 완벽히 이해한 문제는 아닌 것 같습니다 ㅠㅠ..

 

문제 : app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

NumberOfDiscIntersections coding task - Learn to Code - Codility

문제해설

N개의 배열 A가 주어질 때, j = 0~N-1 index로 중심이며, A[j]는 반지름이다. 이때, 원을 그릴 때 겹쳐지는 쌍의 총 갯수를 구하시오.

예를 들어, A = [1, 5, 2, 1, 4, 0]이라는 배열이 있을 경우, 원의 그림은 위와 같이 그려진다.

겹쳐지는 원의 쌍은 (0, 1), (0, 2), (0, 4), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (3, 4), (4, 5)로 11을 return해야한다.

만약, 1,000,000,000을 초과할 경우는 -1을 return한다.

제한 사항

• N은 0~100,000사이
• A의 각 요소는 0~2,147,483,647사이

코드

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

해설

먼저, 배열을 순서대로 한 원의 최저점과 최고점을 list에 담아줍니다. 이 때, 최저점인지 최고점인지 구분하기위해 튜플에 -1과 1을 같이 list에 담아줍니다.

 

그리고 for문을 하나씩 돌면서, 최종 갯수에 중첩해서 쌓고, t에 현재 겹쳐진 disc의 갯수를 체크합니다.