Codility - NumberOfDiscIntersections (Sorting) [Python]

 

 

 문제

 

app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

NumberOfDiscIntersections coding task - Learn to Code - Codility

 

 

 

 

 

 

 문제 상황

 

- 주어진 배열의 인덱스는 각 원의 중심점을 의미한다. 즉, 인덱스 J 번째 원은 (J,0)을 중심으로 하는 원이다. 이 때 다른 원과 교차하는 원들의 쌍의 개수를 구한다. 문제의 조건에 안써있지만, 순서의 개념이 없어 1번 원, 3번 원의 쌍과 3번 원, 1번 원의 쌍은 같은 것으로 취급한다.

 

 

 

 

 

 

 해결 전략

 

 

 

 

 

 

 

 

 코드

 

def solution(A):
    # A를 순회하며 원의 양 끝점을 만든다.
    disc_edge = []
    for i, v in enumerate(A):
        disc_edge.append((i-v, -1)) # 왼쪽 끝
        disc_edge.append((i+v, 1)) # 오른쪽 끝
    disc_edge.sort() # disc_edge를 정렬하여 왼쪽 끝 포인트부터 확인을 시작한다.
    intersection = 0 # 겹치는 원의 개수
    interval = 0 # 열리기 시작하여 아직 닫히지 않은 원의 개수
    for i in range(len(disc_edge)):
        if disc_edge[i][1] == 1 : # 원의 오른쪽 끝
            interval -= 1 # 열려있는 원이 하나 줄어든다.
        if disc_edge[i][1] == -1 : # 원의 왼쪽 끝(새로 열릴 때)
            intersection += interval # 기존에 열려있던 원들과 겹치게 되어 총 쌍의 수에 포함이 된다.
            interval += 1 
    return intersection if intersection <= 10000000 else -1

 

 

 

 

 

 

 

 

 해설

 

- 풀이를 구글링했지만 이해하기 매우 난해했다. 어려웠던 부분은 설명이 없고 변수명만 존재하여 코드를 해석하기 어려웠는데 포인트는 새로운 원이 열릴 때에는 기존에 열려있던 원들과 겹치는 부분이 생기므로 총 쌍에서 더해준다. 닫힐 때에는 열려있는 원만 하나 닫아주면 되므로 결국 포인트는 새로운 원이 열리는 지점을 관찰하는 것이었다.

 

- O(N*log(N)) or O(N)

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 처음 생각한 방법은 O(N^2)의 방법이었다. 겹치는 부분을 생각할 때 포인트만 잡아서 생각하는 것, 결국에는 원이 아니라 수직선의 개념으로 봐도 무방한 문제였다. 

 

- 문제가 애매한 것이 반지름이 0인 상황은 pair를 이룬다고 봐야하나 아닌가의 문제였다. 실제로는 반지름이 0이라면 원이 존재하지 않는 것이므로 pair가 존재하면 안되는데 문제에서는 pair의 개수에 포함하였다.