[프로그래머스] 멀쩡한 사각형 with Python

프로그래머스 멀쩡한 사각형 풀이 공유드립니다.

 

2가지 풀이 방법으로 도전해봤습니다.

 

1. 대각선이 움직일 때마다 사용할 수 있는 상자수를 구해서 더해준다.

출처 : https://lkhlkh23.tistory.com/154

2. 반복되는 패턴에서 빠지는 상자수를 구해서 더해준다.

출처 : https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java

 

 

1, 2번으로 문제에 도전한 결론부터 말씀드리면 1번은 시간 초과 및 계산 오차(6번 케이스)로 실패했고, 2번은 성공했습니다.

 

1번 : 대각선이 이동할 때 마다 사용할 수 있는 상자 수 구하기, 시간 복잡도 : O(n)

출처 : https://lkhlkh23.tistory.com/154

1. 대각선이 아래에서 위로 움직인다고 할때 X에 대응되는 Y값 (높이/너비 * 너비)을 구합니다.

2. 대각선 아래쪽에 사용할 수 있는 모든 상자들의 개수를 더합니다.

• Y값 내림 후 Y보다 작은 모든 자연수만큼 이 사용 가능한 상자 개수입니다.

3. 대각선 아래쪽만 구했으므로 마지막에 사용할 수 있는 상자수 * 2를 Return 합니다

# 시간초과로 실패
# + w, h 입력범위가 1억 이하라서 계산오차로 인한 실패케이스 1개 있음
def solution(w, h):

    answer = 0
    for i in range(w):
        y = i * h / w
        # y 값 내림 후 y보다 작은 모든 자연수만큼이 사용가능한 상자개수입니다.
        answer += int(y)
        
    return answer * 2

• [아래 코드] Decimal 함수를 이용해서 계산 오차 실패 케이스 (6번 케이스)를 처리하긴 했지만 역시나 시간 초과

import math
from decimal import Decimal

def solution_2(w, h):
    answer = 0
    for i in range(w):
        y = i * h / Decimal(w)
        y = math.floor(y)
        answer += y
        
    return answer * 2

2번 : w, h의 최대공약수(Greastest Common Divisor) 주기로 반복되는 패턴으로 공식 도출 , 시간 복잡도 O(1)

출처 : https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java

 

1. 최대공약수(gcd) 만큼 반복되는 패턴이 있다.

2. 패턴은 최대공약수가 1이고 너비(w/gcd), 높이(h/gcd)인 사각형 모양이다.
3. 사각형 패턴 (w/gcd, h/gcd)에서 못쓰는 사각형의 수 구하기

• 패턴(너비, 높이의 최대공약수 1)에서 못쓰는 사각형의 수 : 패턴의 사각형 개수(w/gcd * h/gcd) - 가로선 개수(h/gcd -1) - 세로선 개수(w/gcd -1) - 1(최초 사각형)
• 사용 가능한 사각형 최종 공식 유도하기 중간 과정
  • w/gcd = wg, h/gcd = hg로 치환 (wg*최대공약수 = w, hg*최대공약수 = h)
  • 사용 가능한 전체 사각형 수 = 최대공약수 * {wg * hg - (wg-1) - (hg-1) -1} ← 이식의 상수를 한번 밖으로 빼고
  • 최대공약수 * {wg * hg - wg - hg +1} ← 마지막으로 괄호를 풀어주면
  • w * h - w - h + 최대공약수
• 사용가능한 사각형 최종 공식 : w * h - (w + h - 최대공약수)

최대공약수 개수만큼 발생하는 패턴에서 사용 못하는 사각형 구해서 풀기

전체 사각형 개수 - (패턴에서 사용못하는 사각형 개수 * 패턴 반복수(최대공약수))

# 패턴에서 사용못하는 사각형 개수 구해서 풀기
def solution_2(w, h):
    
    # 최대공약수(gcd, Greatest Common Divisor) 구하는 함수
    def ucld_gcd(x, y):
        if y == 0:
            return x
        else:
            return ucld_gcd(y, x%y)    

    gcd = ucld_gcd(w, h)
    sub_w = int(w / gcd)
    sub_h = int(h / gcd)
    # 패턴에서 사용못하는 사각형 개수 구하기
    sub_whiteblock = sub_w + sub_h - 1
    
    # 최종 사각형 개수 구하기
    answer = w * h - (gcd * sub_whiteblock)
    return answer

유도한 전체 공식으로 한 번에 풀기

def solution_3(w, h):
    
    def ucld_gcd(x, y):
        if y == 0:
            return x
        else:
            return ucld_gcd(y, x%y)
    
    gcd = ucld_gcd(w, h)
    answer = w * h - (w + h - gcd)
    
    return answer

궁금하신 사항은 댓글 남겨주세요.

 

감사합니다.