멀쩡한 사각형(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

문제 접근 방식

전체 사각형의 모서리를 대각선으로 이었을 때 잘려진 부분을 제외한 나머지 온전한 사각형의 개수를 구하는 문제이다. 이차원 좌표공간에서 직선으로 보았으며 기울기에 따라 잘려지는 사각형의 개수가 정해지기 때문에 기울기를 활용하려고 하였다. 아래와 같은 방식으로 문제를 접근했으며, 중간에 시간초과가 나는 부분이 있어서 힌트를 보고 마저 풀었다.

1. 전체 사각형의 너비를 1씩 순회하면서 잘려진 사각형의 개수를 모두 구하고, 이를 전체 사각형 개수에서 빼준다
>> 이렇게 진행할 경우, 전체 width에 대해 for문이 수행되며 width의 최대가 1e8이므로 시간 초과가 난다

2. 최대공약수를 활용한 공통 모양 추출
>> 예시를 보면, 특정 모양 4개가 반복되면서 그려지는 것을 볼 수 있다.
>> 이는 너비, 높이의 최대 공약수를 구하여, 각각을 최대공약수로 나눠서 공통 모양을 구한다.
>> 해당 공통 모양에 대해 잘리는 사각형 개수를 구하고, 반복되는 횟수만큼 곱해서 전체 잘린 사각형 수를 구한다

3. 2번을 거쳤음에도 불구하고 1개의 케이스에서 시간초과가 발생했고, 힌트를 참고했다.
>> 11번 시간초과였는데, 너비가 높이에 비해 상대적으로 긴 경우가 존재한다
>> 이럴 경우, 높이를 기준으로 for문을 돌리면 조금더 빠르게 실행할 수 있다.

 

 

시간 복잡도

처음 풀이의 경우, 너비 W만큼 for문 1번을 돌게 되며, 이때 너비의 최대값이 1e8이기 때문에 아슬하게 통과할 것으로 예상했다. 하지만 시간초과가 발생했고, 이를 줄이기 위해 반복되는 공통 모양에 대해 for문을 돌게하여 시간을 단축시킬 수 있었다(정확한 수치는 예상 X) 

 

 

코드

from math import ceil,floor

def get_gcd(a,b):
    if a<b:
        a,b=b,a
    
    dividend,divisor=a,b
    while True:
        if dividend%divisor==0:
            break
        temp=dividend%divisor
        dividend=divisor
        divisor=temp
    return divisor

def solution(w,h):
    previous=0
    triangle=0
    gcd=get_gcd(w,h)
    if h<w:
        w,h=h,w
    uw,uh=w//gcd,h//gcd
    for i in range(1,uw+1):
        #부동소수점 오차 발생 if uh/uw*i 로 진행시
        current=uh*i/uw
        triangle+=ceil(current)-floor(previous)
        previous=current
    return w*h-triangle*gcd

 

 

회고

3번의 과정을 거쳐서 통과를 할 줄 알았으나 오히려 testcase 2, 17번에서 에러가 발생했다. 논리적으로는 오류가 없었는데도 불구하고 에러가 발생해서 검색을 하였고, 소수를 처리하는 과정에서 에러가 발생하는 것으로 확인했다. <변경 전 코드> 와 <변경 후 코드>는 나누기의 순서를 제일 나중에 함으로써 계산의 정확도가 차이난다는 것을 보여준다.

 

변경 전 코드

for i in range(1,uw+1):
    #부동소수점 오차 발생 if uh/uw*i 로 진행시
    current=uh/uw*i

 

 

변경 후 코드

for i in range(1,uw+1):
    #부동소수점 오차 발생 if uh/uw*i 로 진행시
    current=uh*i/uw