[구현] 멀쩡한 사각형 - level2

[heerucan]

https://school.programmers.co.kr/learn/courses/30/lessons/62048

문제 설명

• w, h의 최대공약수가 1이면 -> w+h-1
• 1보다 크면 -> w+h-최대공약수
• 정사각형이면 -> 한 변의 개수 -> w

# 사용할 수 있는 정사각형 개수를 반환

def solution(w,h):
    answer = 0
    total = w*h
    
    gcdArr = [] # 공약수 배열
    greatestValue = 0 # 최대공약수
    
    for i in range(min(w,h), 0, -1):
        if w % i == 0 and h % i == 0:
            gcdArr.append(i)
    
    greatestValue = gcdArr[0]
                
    if greatestValue == 1:
        answer = total-(w+h-1)
    elif w == h: # 정사각형의 경우
        answer = total-w
    elif greatestValue > 1:
        answer = total-(w+h-greatestValue)
    
    return answer

solution(8,12)

문제 풀이

• 최대공약수를 구할 때 for문을 여러번 사용해 시간초과가 날 것 같다는 생각했는데, 아니나 다를까.. 그래서 개선하고 개선했는데,, set intersection을 썼는데 시간초과가 해결되지 않았다.
• 최대공약수를 구하기 위해서는 두 수 중 작은 수의 약수들 중에서 a,b를 나눠떨어지게 하는 수를 구하면 된다. 또는 math 라이브러리 쓰기
• 해당 문제에 어떤 규칙이 있는지 파악하는 것이 약간 어려웠다...