Lesson 6 - NumberOfDicIntersection

자세한 문제는 여기서 확인하시면 됩니다.

 

이 문제는 array의 index가 위치고 그 값이 반지름이되어 원들이 겹치는 횟수를 반환하는 문제입니다.

 

예제의 겹치는 횟수는

 

0, 1 / 0, 2 / 0, 4
1, 2 / 1, 3 / 1, 4 / 1, 5
2, 3 / 2, 4
3, 4
4, 5

 

이렇게 겹쳐지기 때문에 11입니다.

 

첫번째 알고리즘을 사용한 방법은  O(N**2) 복잡도를 나타냈습니다. 그리고 결과는 75%

 

fun solution(A: IntArray): Int {
    var count = 0
    for(i in A.indices){
        for( j in i+1 until A.size){
            if(j-A[j]<=i-A[i] && j+A[j]>=i+A[i]){
                count++
            }else if(i-A[i]<=j-A[j] && i+A[i]>=j-A[j] ){
                count++
            }
        }
        if(count > 10000000){
            return -1
        }
    }

    return count
}

단순하게 다음 원안에 현재 원이 포함되어 있거나 현재원 안에 다음원의 좌측 부분이 포함되어있으면 count를 하는 방법으로 했습니다.

 

그랬더니 역시나 많은 값을 계산 할 때는 timeout이 발생하고 있었습니다. (그리고 한가지 예시에 답이 2인데 자꾸 0을 반환하고 있었습니다.)

 

아무리 머리를 굴려도 답이 나오지 않아서 구글링을 해보았습니다.

 

그랬더니 각 좌표의 시작과 끝을 정렬한 후 시작점이 끝점보다 작은 디스크는 모두 겹치기 때문에 이 갯수를 세면 된다고 합니다.

 

위의 내용을 토대로 만들어지 code가

fun solution(A: IntArray): Int {
     var result = 0
    val dps = IntArray(A.size)
    val dpe = IntArray(A.size)

    for( i in A.indices){
        var s = if(i>A[i]){
            i-A[i]
        }else{
            0
        }
        var e = if(A.size-1-i > A[i]){
            i+A[i]
        }else{
            A.size -1
        }
        dps[s]++
        dpe[e]++
    }

    var t = 0

    for (i in A.indices){
        if(dps[i]> 0){
            result += t * dps[i]
            result += dps[i]*(dps[i]-1)/2
            if(10000000<result) return -1
            t += dps[i]
        }
        t -= dpe[i]
    }
    return result
}

 

결과는 100%에 복잡도는 O(N*log(N)) or O(N) 이렇게 나타나고 있습니다