[프로그래머스][LV.1] 최소직사각형 | python3

 

문제 링크: 최소직사각형

 

문제 설명

문제 설명

명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.
모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

제한사항
- sizes의 길이는 1 이상 10,000 이하입니다.

• sizes의 원소는 [w, h] 형식입니다.
• w는 명함의 가로 길이를 나타냅니다.
• h는 명함의 세로 길이를 나타냅니다.
• w와 h는 1 이상 1,000 이하인 자연수입니다.

 

---

문제 풀이

for문으로 sizes의 배열들의 각각의 1차원 배열 원소를 sort하여 작은것들은 작은것끼리, 큰것들은 큰것끼리 같은 인덱스에 있을 수 있도록 하였다.

 그리고 같은 인덱스에 있는 것들 중에서 가장 큰 것들을 골라서 곱해주면 된다. 

 

내코드

<예전 풀이>

def solution(sizes):
    for idx in range(len(sizes)):
        sizes[idx].sort()
    n,m=0,0
    for a,b in sizes:
        n=max(n,a)
        m=max(m,b)
    answer=n*m
    return answer

 

< 다시 푼 풀이>

def solution(sizes):
    answer = 0
    w=0
    h=0
    for size in sizes:
        size.sort()
        w=max(w,size[1])
        h=max(h,size[0])
        
    answer=w*h
    return answer

 

---

다른사람풀이

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

결국 작은 것들 중 큰 것, 큰 것들 중 큰 것을 구하는 것이기 때문에 미리 sort를 쓰지 않아도 되는구나...

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

 

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])

 

♣ sum 함수

sum() 함수는 Python 내장 함수로, 숫자들의 합을 구하거나 iterable을 합칠 때 사용됩니다. 코드에서 sum(sizes, [])가 쓰인 방식은 리스트를 평탄화(flatten)하는 데 사용되었습니다.

자세히 살펴보면:

• sizes는 2차원 리스트(리스트 안에 리스트가 있는 형태)로 가정됩니다. 예: sizes = [[1, 2], [3, 4], [5, 6]].
• sum(iterable, start)의 역할은 start 값을 기준으로 iterable을 모두 더하는 것입니다.
  • 여기서 start=[]로 빈 리스트를 제공하면, sizes의 모든 리스트가 합쳐져 하나의 리스트가 됩니다.
  • interable와 start 값이 같은 값이어야 함.
  • 만약 숫자라면 sum([1,2,3,4],10) 이라면 10+1+2+3+4
  • 문자열을 sum()함수와 함께 사용 불가

sum(sizes, []):

• sizes에 있는 각 리스트를 빈 리스트 []에 더하면서 하나의 리스트로 합칩니다.
• 결과: [1, 2, 3, 4, 5, 6]

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

 if 문을 사용하여 크기를 비교한 후 작은값, 큰값이면 위치 바꾸기

 

def solution(sizes):
    answer = []
    
    sorted_w = sorted(sizes, key=lambda x: x[0]) # 가로기준 정렬
    sorted_h = sorted(sizes, key=lambda x: x[1]) # 세로기준 정렬
    max_w = sorted_w[-1][0] # 80
    max_h = sorted_h[-1][1]  # 70

    if max_w >= max_h:
        min_h = sorted_w[-1][1]
        for size in sorted_w[:-1]:
            if min(size) > min_h:
                min_h = min(size)
        answer = [max_w , min_h]
    else:
        min_w = sorted_h[-1][0]
        for size in sorted_h[:-1]:
            if min(size) > min_w:
                min_w = min(size)
        answer = [min_w , max_h]

    return answer[0]*answer[1]

 

이 코드가 정말 이해가 안됐는데 결국 알아냈다.

가로와 세로를 각각 정렬하여 가장 큰 값을 찾는다.

그리고 그 두 수를 비교하여 가로가 더 크다면 가로를 고정하여 (가로가 더 긴 면이라고 생각) 

세로길이 중 가장 긴 길이를 찾는다.

if 조건문에서 min(size) 가 뜻하는 것이 세로길이를 뜻하는 거였다. (가로 길이가 더 길다고 가정했기때문에)

세로길이가 더 길때도 똑같이 세로 길이가 더 길다고 가정하여 풀면 된다.