264. NumberOfDiscIntersections

1. Javascript

참고

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    let array = new Array();
    let intersect = 0;
    
    for(let i=0; i<N; i++){
        let circle = {
            left: i - A[i],
            right: i + A[i]
        }
        array.push(circle);
    }
    array.sort((a, b) => a.left - b.left );
    
    for(let i=0; i<N-1; i++){
        for(let j=i+1; j<N; j++){
            if(intersect > 10000000){
                return -1;
            }
            if(array[j].left > array[i].right){
                break;
            }
            if(array[j].left >= array[i].left && array[j].left <= array[i].right){
                intersect++;
            }
        }
    }
    
    return intersect;
}

2. Python

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