[codility] RectangleBuilderGreaterArea 문제 파이썬

문제 https://app.codility.com/programmers/trainings/2/rectangle_builder_greater_area/start/

Codility

 

 

from collections import Counter
import itertools

def solution(A, X):
    counterDict = Counter(A)
    answer = 0
    candidateArr = []
    for k, v in counterDict.items():
        if (v>1):
            candidateArr.append(k)

        if (v>3) and k*k>=X:
            answer+=1
            
    combination = list(itertools.combinations(candidateArr,2))
    resultArr = [(x,y) for x, y in combination if x*y>=X]
    answer = answer + len(resultArr)

    if (answer>1000000000):
        return -1

    return answer

무지성으로 풀었더니 시간 초과ㅋㅋㅋ 예상하긴 함

조합을 직접 구해버리면 시간복잡도가 n*n라 다른 방법을 생각해 본다.

X보다 작아지면 더 작은것들은 계산 하지 않도록. 

빅오 엔제곱이 나옴

스코어는 69%

 

완성 코드

from collections import Counter

def solution(A, X):
    counterDict = Counter(A)
    answer = 0
    candidateArr = []
    for k, v in counterDict.items():
        if (v>1):
            candidateArr.append(k)

        if (v>3) and k*k>=X:
            answer+=1

    candidateArr.sort()  
    i = 0
    j = len(candidateArr) - 1
    while i < j:
        if candidateArr[i] * candidateArr[j] >= X:
        	answer += j - i
            if answer > 1000000000: 
                return -1
            j -= 1
        else:
            i += 1
    return answer

완성