Level 2 카펫 Python3

https://programmers.co.kr/learn/courses/30/lessons/42842?language=python3 

코딩테스트 연습 - 카펫

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_카펫.py

hwayeon351/Programmers-Algorithms

from math import sqrt

def solution(brown, yellow):
    total = brown+yellow
    for i in range(3, int(sqrt(total))+1):
        if total % i !=0: continue
        j = total//i
        if (i-2) * (j-2) == yellow:
            return [j,i]

---

풀이 과정

풀이 시간 15분

from math import sqrt

def solution(brown, yellow):
    #1. 총 격자 수
    total = brown+yello
    #2. 가능한 카펫 모양 구하기(약수 찾기)
    for i in range(3, int(sqrt(total))+1):
        if total % i !=0: continue
        j = total//i
        #3. 노란색 격자 개수와 일치하면 정답 return
        if (i-2) * (j-2) == yellow:
            return [j,i]
#시간복잡도=O(log N) 공간복잡도=O(N)

먼저, brown + yellow인 총 격자 수를 활용하여 가능한 카펫 모양 종류를 구하고 해당 카펫의 노란 격자 개수가 yellow와 일치하는지를 체크한다. 예를 들어 brown = 24, yellow = 24라면 total = 48이고, 가능한 카펫 모양은 (3, 16), (4, 12), (6, 8) 3가지가 있다. 이 중에 노란색 격자 개수와 일치하는 카펫 모양은 (6, 8)이므로 정답은 [8, 6]이 된다.