[Python] 프로그래머스 lv.1 최소직사각형

알고리즘 고득점 kit - 완전탐색 - (1)

 

문제 분석

• 지갑의 최소 크기 구하기

 

코드 설계

• 조합 (combination)
• 0부터 명함 개수 + 1개 만큼의 조합 구하기 (ex. 명함 개수 : 6개 → 0~6 : 7개)
  • 0 : 아무것도 바뀌지 않음
  • 1 : 6개 중 하나만 바뀜 (0,1,2,3,4,5 중 1개)
  • 2 : 6개 중 2개 바뀜 (0,1), (0,2), (0,3) ... (5,6)
  • ...
  • 6 : 6개 전부 바뀜
• 나온 숫자의 1차원 인덱스 위치 1 / 2차원 값 바꾸기
• 그 중 가로x세로가 최소 크기인 경우 구하기

했는데.. 조합의 개수가 다를 때 어떻게 인덱스로 가져와야 할지 모르겠음.. 

 

정답 코드

실패

from itertools import combinations

def solution(sizes):
    answer = 0
    num = []
    for i in range(len(sizes)):
        num.append(i)

    for i in range(len(sizes)+1): # 전부 출력되는 경우도 있어야 하니까 길이 + 1
        for j in combinations(num, i+1):
            print(j)
    return answer

s = [[60, 50], [30, 70], [60, 30], [80, 40]]
print(solution(s))

 

다른 사람 코드 1 ( https://smcho1201.tistory.com/83 )

def solution(sizes):
    w = []
    h = []
    for s in sizes :
        w.append(max(s))
        h.append(min(s))
    return max(w) * max(h)

• 명함의 가로, 세로가 서로 바뀌어도 상관 x
• 이 문제에서의 return 값은 가로, 세로 길이가 아닌 넓이
• 각 명함의 긴 길이를 비교하여 최대값을 찾는다.

 

2회차 - 2024.12.01

• 모든 명함을 수납할 수 있는 가장 작은 지갑의 크기
• 회전시켜 겹쳤을 때, 모든 명함을 포함하는 가장 작은 지갑의 크기

• 전체 값 중 가장 긴 길이 : 왜냐면 가장 긴 길이는 어떻게 돌려도 가장 긴 길이이기 때문에 꼭 한 면이 되어야 함 (ex 세로)
• 그리고 남은 명함들의 가로 세로 중 길이가 더 작은 것만 골랐을 때 그 중 가장 큰 값을 가로로 선정

 

정답 코드

def solution(sizes):
    answer = 0
    max_w = float('-inf')
    min_h = []
    
    for w,h in sizes : 
        max_w = max(w,h,max_w)
        min_h.append(min(w,h))
    
    answer = max_w * max(min_h)
    return answer

 

다른 사람 코드 1

def solution(sizes):
    return max(max(x) for x in sizes) * max(min(x) for x in sizes)

 

다른 사람 코드 2

def solution(sizes):
    row = 0
    col = 0
    for a, b in sizes:
        if a < b:
            a, b = b, a
        row = max(row, a)
        col = max(col, b)
    return row * col

 

다른 사람 코드 3

solution = lambda sizes: max(sum(sizes, [])) * max(min(size) for size in sizes)

 

다른 사람 코드 4

def solution(sizes):
    sizes = [sorted(s) for s in sizes]
    return max([x[0] for x in sizes]) * max([x[1] for x in sizes])