코딜리티 L6_NumberOfDiscIntersections 파이썬 (라인 스위핑)

2023-03-18

Codility L6_NumberOfDiscIntersections 파이썬

참고: NumberOfDiscIntersections coding task - Learn to Code - Codility

무엇?

1. N개의 디스크를 표현하는 배열 A이 주어짐.
2. 서로 겹치는 원 쌍의 개수를 리턴
3. 10000000개가 넘으면 -1 리턴

어떻게?

라인 스위핑 (O(N*log(N)) or O(N))

1. left edge, right edge 구분
2. 좌표상 위치와, left edge를 기준으로 오름차순 정렬(※ 중요)
3. 정렬한 것들에 대해서
   1. left edge를 만나면(또 다른 원이 시작한다는 뜻):
      1. 인터섹트에 액티브 디스크 수만큼 추가
      2. 액티브 디스크 += 1
   2. right edge를 만나면(원 하나가 끝났다는 뜻) 액티브 디스크 -= 1

def solution(A):  # Detected time complexity: O(N*log(N)) or O(N)

    discs = []
    active_discs = 0
    intersect = 0

    for i, radius in enumerate(A):
        discs.append((i - radius, 1))
        discs.append((i + radius, -1))
    discs.sort(key=lambda x: (x[0], -x[1]))

    for _, edge in discs:
        if (edge == 1):
            intersect += active_discs
            if (intersect > 10000000):
                return -1
            active_discs += 1
        else:
            active_discs -= 1
    return intersect

try-error

1. 정렬할 때 left edge가 먼저 오도록 신경써야 함. 그렇지 않으면 제대로 disc 수가 카운트 되지 않음