[codility] NumberOfDiscIntersections

app.codility.com/c/run/trainingPURC2R-CMA/

Codility

음... 문제 이해를 잘못했다

교차점의 개수를 구하는 줄 알앗는데 디스크끼리 겹쳐지는 개수를 구하는 거 였다

(디스크 안에 디스크가 있어도 겹쳐져 있다고 생각함)

↓ 틀린 풀이

def solution(A):
    # write your code in Python 3.6
    count = 0
    for i in range(len(A)-1):
        print("----")
        for j in range(i+1,len(A)):
            print(i+A[i], j+A[j], i+A[i], j-A[j])
            if i+A[i] == j+A[j] or i+A[i] == j-A[j]:
                count +=1
            elif i+A[i]> j-A[j] or i+A[i]> j+A[j]:
                count +=2
            print(i,j,count)
    return count

이분 블로그에 있는 코드가 제일 이해하기 쉬웠다ㅠㅠ : m.blog.naver.com/evanecen/221359303451

(원의 중심-반지름,-1), (원의 중심+반지름,1) 로 나누어서 새로운 배열을 만들고

tuple의 맨 앞의 값으로 정렬해준다

-1일 때 괄호를 열고 1일 때 괄호를 닫는다는 생각으로 문제를 바꿔보자

 

-1일 때 괄호를 여니까 count를 1씩 증가해주고

1일 때 괄호를 닫으니까 count를 1 빼주고 남은 count를 intersection에 더한다

(count 1개는 본인 거니까 1을 빼줘야 다른 괄호가 내 거를 셀 때 중복되지 않는다)

와 한 4시간동안 고민하고 조오금 이해했다

def solution(A):
    # write your code in Python 3.6
    d = []
    for i, v in enumerate(A):
        d.append((i-v,-1))
        d.append((i+v,1))
    d.sort()
    #print(d)
    intersection = 0
    count = 0
    for i,v in enumerate(d):
        if v[1] == -1:
            count += 1 
        if v[1] == 1:
            count -= 1
            intersection += count
        if intersection > 10000000:
            return -1
    return intersection