Codility RectangleBuilderGreaterArea

이 문제는 N이 100,000개 까지 나올 수 있으므로 N^2 이상의 알고리즘으로 풀면 안됩니다.

다행히 펜스의 너비가 같더라도 가로와 세로길이가 다르면, 다른 종류의 펜스로 인정하니

만들수 있는 장대의 길이를 오름차순으로 정렬하여 어떤 index부터 X의 너비이상을 만족하는지 찾으면 N*log(N) 시간에 펜스의 종류를 확인할 수 있습니다.

 

1. 같은 길이의 장대가 2개 이상인 장대를 list에 할당한다.

2. 장대를 하나 정하고(A) 그 장대로 X너비 이상의 펜스를 만들 수 있는 최소길이의 장대(B)를 찾는다. (이분탐색) 

3. 전체 장대길이 - 최소길이의 장대(B) index한 만큼 만들 수 있는 펜스의 종류이므로 이 값을 누적시킨다.

4. A 장대가 4개 이상이면, A장대만으로 펜스를 만들 수 있으므로 1을 더 누적시킨다.

 

def solution(A, X):
    answer = 0
    counts = {}
    for a in A:
        if a in counts:
            counts[a] += 1
        else:
            counts[a] = 1
    fences = []
    for key in counts:
        if counts[key] >= 2:
            fences.append(key)
    fences.sort()
    size = len(fences)
    for pivot in range(size):
        left = pivot
        right = size - 1

        while left <= right:
            mid = (left + right) // 2
            if fences[pivot] * fences[mid] >= X:
                right = mid - 1
            else:
                left = mid + 1
        mid = left
        answer += (size - mid)
        if counts[fences[pivot]] < 4 and pivot == mid: answer -= 1
        if answer > 1000000000: return -1
    return answer

이 때 주의할 점은 B장대를 탐색하는 이분탐색시, A와 B장대로 만들 수 있는 가장작은 수 이므로 mid값이 아닌, 이분탐색을 탈출했을 때의 left값을 index로 지정합니다.

그리고 누적값이 1,000,000,000을 넘어가면, -1을 리턴하는 것을 잊지 않습니다:)