멀쩡한 사각형

 

코딩테스트 연습 - 멀쩡한 사각형 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 풀이

def gcb_aksu(num1, num2):
    answer=0
    set_1 = set()
    set_2 = set()
    for i in range(1, int(num1**(1/2))+1):
        if num1%i==0:
            set_1.add(i)
            if i**2!=num1:
                set_1.add(num1//i)
    for i in range(1, int(num2**(1/2))+1):
        if num2%i==0:
            set_2.add(i)
            if i**2!=num2:
                set_2.add(num2//i)
    answer = max(set_1&set_2)
    return answer

def solution(w,h):
    answer = 0
    common_point = gcb_aksu(w,h)
    answer = w*h - (((w//common_point)+(h//common_point)-1)*common_point)
    return answer

 

1) 최대 공약수로 교점의 갯수를 구하고

2) 사용할수 없는 사각형수 (가로+세로-1) * 최대 공약수

 

시간 복잡도 

1. for i in range(1, int(num1**(1/2))+1) : 입력 크기의 제곱근을 순회 [ O(√n)  ]

2. 내부 연산은 상수시간 [  O(1)  ]

3. 최종 연산도 상수시간 [  O(1)  ]

 

최종 시간 복잡도 : O(√n)