[Python] 프로그래머스 lv.1 카펫

 

문제 분석

• 중앙 노란색, 테두리 1줄은 갈색의 격자 모양 카펫
• 집으로 돌아와서 카펫의 노란색과 갈색이 색칠된 격자의 개수는 기억했지만, 
• 전체 카펫 크기는 기억하지 못함
• leo가 본 카펫에서 갈색 격자의 수, 노란색 격자의 수가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return
• 카펫의 길이는 가로가 더 길다.

 

코드 설계

• 노란색을 감쌀 수 있는 갈색 테두리 1줄

• 어차피 전체 카펫의 길이를 구하는거
• 총 격자 개수 값이 나올 수 있는 두 수의 곱을 모두 구한 뒤,
• 카펫이 정사각형이 되거나 가로가 조금 더 긴? 경우의 수 return

• 두 수의 곱이 격자 개수의 합이 될 수 있는 두 수를 구할 것인가
• 두 수의 곱이 될 수 있는 수 : 약수
• 완탐 : 모든 경우의 수를 구하고 // 순서 상관 x, 중복o → 중복 조합

• 1 ~ 합(len)//2 까지의 모든 조합을 찾는데
• 만약 그 곱이 len과 같으면 답 후보에 넣고
• 그 중 두 값의 차가 가장 작은 거 구하기
• 차가 없다면 그냥 두개 넣고, 차가 있다면 큰 수 먼저

 

정답 코드

1차 - 실패 : 테스트 케이스 통과 못함 & 시간 초과 (46.2점)

from itertools import combinations_with_replacement

def solution(brown, yellow):
    answer = []
    carpet = brown + yellow
    arr = [i for i in range(1, carpet//2+1)]

    pos = []
    for r in combinations_with_replacement(arr, 2) :
        n1, n2 = r
        if n1 * n2 == carpet :
            pos.append(r)

    min_v = float('inf')
    col, row = 0, 0
    for i in pos :
        n1, n2 = i
        if min_v > abs(n1 - n2) :
            min_v = abs(n1 - n2)
            if n1 >= n2 :
                col = n1
                row = n2
            else :
                col = n2
                row = n1

    answer.append(col)
    answer.append(row)
    return answer

 

2차 코드 - 실패 (46.2점)

from itertools import combinations_with_replacement

def solution(brown, yellow):
    answer = []
    carpet = brown + yellow
    arr = [i for i in range(1, carpet//2+1)]

    pos = []
    for r in combinations_with_replacement(arr, 2) :
        n1, n2 = r
        if n1 * n2 == carpet :
            pos.append(r)

    # pos.sort() # 어차피 처음 부터 해서 정렬될 것?
    row, col = pos[-1]
    answer.append(col)
    answer.append(row)
    return answer

 

다른 블로그를 봤는데 이렇게 풀면.. 안되나보다..

 

다른 사람 코드 1

• 노란색의 가로, 세로 칸 수를 이용
• 결국 구해야하는 문제는 노란색의 가로 길이 + 2, 노란색의 세로 길이 + 2
• 이거를 (yellow 가로 * 2) + (yellow 세로 * 2) + 4 값이 갈색 격자의 수와 같으면 된다

def solution(brown, yellow):
    ans = []

    yellow_x = 0
    yellow_y = 0

    for i in range(1, yellow+1) :
        if yellow % i == 0 : # 노란색 수가 i로 나눠 떨어지면
            yellow_x = int(yellow/i) # 가로 : 노란색을 i로 나눈 몫
            yellow_y = i # i는 세로(i가 작은 수 부터 증가하니까 더 작을것)

            if yellow_x * 2 + yellow_y * 2 + 4 == brown :
                ans.append(yellow_x+2)
                ans.append(yellow_y+2)

                return sorted(ans, reverse=True)
    return ans

 

다른 사람 코드 2

def solution(brown, yellow):
    answer = []
    total = brown + yellow                  # a * b = total
    for b in range(1,total+1):
        if (total / b) % 1 == 0:            # total / b = a
            a = total / b
            if a >= b:                      # a >= b
                if 2*a + 2*b == brown + 4:  # 2*a + 2*b = brown + 4 
                    return [a,b]
            
    return answer

 

다른 사람 코드 3 - 근의 공식

import math

def solution(brown, yellow):
    w = ((brown+4)/2 + math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    h = ((brown+4)/2 - math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    return [w,h]