[Codility] 코딜리티 6-3. NumberOfDiscIntersections (Python)

안녕하세요! 이번 문제는 제 힘으로 100%를 만들지 못했습니다. 시간 복잡도를 줄이는 것이 너무 어렵네요.

100점짜리 알고리즘은 출처도 같이 올려드리겠습니다.

 

이전 코드 내용이 궁금하시다면 아래 링크로 이동하시면 됩니다!

코딜리티 이전 글 - 2020/08/18 - [데이터 분석/파이썬] - [Codility] 코딜리티 6-2. MaxProductOfThree (Python)

[Codility] 코딜리티 6-2. MaxProductOfThree (Python)

---

1. 문제 설명

• A의 index는 원의 중심, A의 value는 원의 반지름을 나타낸다.
• A가 intersection되는 값들을 합해서 출력해줘야 한다.
• intersection 수가 10000000를 초과하면 -1을 출력해야 한다.

2. 1차 풀이 (시간 복잡도 : N**2)

• idea : for문 2개를 이용해서 아래쪽 원의 가장 우측 값보다 오른쪽 원의 가장 좌측 값이 작거나 같으면 1씩 증가시키도록 했습니다.
• Task score : 56, Correctness : 100, Performance : 12

def solution(A):
    count = 0
    for i in range(len(A)-1):
        for j in range(i+1, len(A)):
            if i+A[i]>=j-A[j]:
                count +=1
    if count > 10000000:
        count = -1
    return count

3. 2차 풀이 (시간 복잡도 : N*log(N) or N)

• idea : 각 원의 가장 작은 값과 -1을 튜플로, 가장 큰 값과 1을 튜플로 묶어서 한 리스트에 저장한다.
  그 리스트를 sort로 해서 -1인 값이 나오면 intervals을 더하고, intervals을 1개씩 추가합니다.
  1인 값이 나오면 intervals을 1 뺍니다.(원이 하나 완성이 된 것)
• 참고한 블로그 출처 : https://datacodingschool.tistory.com/33

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

    arr.sort()
    intersection = 0
    intervals = 0

    for i,v in enumerate(arr):
        if v[1] == 1 :
            intervals -= 1
        if v[1] == -1:
            intersection += intervals
            intervals += 1
    if intersection > 10000000:
        intersection = -1

    return intersection