[프로그래머스 lv.1]최소직사각형(건너뛴 문제 다시풀기)

묘걍 2023. 9. 20. 16:10

문제

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

아래 표는 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문을 돌면서 첫 번째 요소는 hori리스트에 두 번째 요소는 verti 리스트에 append한다.

각 리스트를 내림차순 정렬 하고

리스트의 [0]번째 요소를 가져오면 최대 길이다.

그 값을 우선 horizontal과 vertical 변수에 대입한다.

(max() 이용해도 되긴 하는데 나중에 정렬된 리스트가 필요할 것 같아서)

가로로 눕혔을 때 가능한 차선책

'세로길이 중 최대 값'이 '가로 길이의 최대값'보다 작을 경우

'세로길이 최대값의 가로길이'가 '가로길이 최대값의 세로길이'보다 작은지 확인하고

모두 만족한다면 '가로길이 최대'와 '세로길이 중 두 번째로 긴 길이'로 한다.

세로로 눕혔을 때 가능한 차선책

'가로 길이 중 최대 값'이 '세로 길이의 최대값'보다 작을 경우

'가로 길이 최대값의 세로길이'가 '세로 길이 최대값의 가로길이'보다 작은지 확인하고

모두 만족한다면 '세로길이 최대'와 '가로 길이 중 두 번째로 긴 길이'로 한다.

answer = 가로 * 세로

코드

def solution(sizes):
    answer = 0
    hori = []
    verti = []
    horizontal = 0
    vertical = 0
    for i in range(len(sizes)):
        hori.append(sizes[i][0])
        verti.append(sizes[i][1])
    hori = sorted(hori, reverse=True)
    verti = sorted(verti, reverse=True)
    horizontal = hori[0]
    vertical = verti[0]
    
    fir_verti = 0
    fir_hori = 0
    # 가로로 눕혔을 때 가능한 차선책
    if vertical < horizontal:
        for i in range(len(sizes)):
            if sizes[i][1] == vertical:
                fir_hori = sizes[i][0]
            if sizes[i][0] == horizontal:
                fir_verti = sizes[i][1]
            if fir_hori < fir_verti:
                vertical = verti[1]
    
    # 세로로 눕혔을 때 가능한 차선책
    if horizontal < vertical:
        for i in range(len(sizes)):
            if sizes[i][0] == horizontal:
                fir_verti = sizes[i][1]
            if sizes[i][1] == vertical:
                fir_hori = sizes[i][0]
            if fir_verti < fir_hori:
                horizontal = hori[1]
    answer = horizontal * vertical

    return answer

다시 생각해보기

생각

똑같이 밖에 생각이 안 난다

코드

다른 사람 풀이

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

코드 스스로 해석하고 이해하기

- 각 명함의 사이즈에서 가장 긴 변의 길이를 가져온다

- 각 명함의 사이즈에서 가장 짧은 변의 길이를 가져온다

- 긴 변들의 길이 중에서도 긴 길이를 찾는다

- 짧은 변의 길이들 중에서 긴 길이를 찾는다

- 두 값을 곱한다

def solution(sizes):
    # 1. 명함 지갑의 가로, 세로 길이 후보 list 변수 w, h 생성한다
    w = []  # 명함 지갑의 가로 길이 후보 리스트
    h = []  # 명함 지갑의 세로 길이 후보 리스트
    
    # 2. 주어진 명함들을 for 문을 돌면서 더 큰 값을 w, 작은 값을 h에 저장한다
    for size in sizes:
        if size[0] > size[1]:
            w.append(size[0])
            h.append(size[1])
        else:
            w.append(size[1])
            h.append(size[0])     
    
    # 3. 각 w, h 리스트에서 가장 큰 값을 곱한다
    return max(w) * max(h)

코드 스스로 해석하고 이해하기

- 가로길이 후보들을 저장할 빈 리스트

- 세로길이 후보들을 저장할 빈 리스트

- sizes를 for문 돌면서

- 만약 한 명함의 가로길이가 세로길이보다 길다면

각각을 빈 리스트에 추가해주고

- 그렇지 않다면 (세로길이가 더 길면)

반대로 넣어준다.

- 각 리스트에서 최대값끼리 곱해준다

명함의 가로, 세로 길이 중 더 큰 값의 최댓값, 더 작은 값의 최댓값을 곱한 값이 정답이었다.

예시를 들어 설명하면 이해가 가는데 문제만 봐서는 이런 생각을 못하겠다