[ Python ] 최소직사각형

[Programmers/Python] 최소직사각형 풀이 정리

문제 링크: Programmers - 최소직사각형

2차원 리스트를 순회하면서 각 명함의 가로와 세로를 정리하고, 모든 명함을 담을 수 있는 최소 지갑 크기를 구하는 문제다.

문제 핵심

명함의 크기들이 sizes에 담겨 있을 때, 모든 명함을 넣을 수 있는 가장 작은 지갑의 넓이를 구하는 문제다. 명함은 회전할 수 있으므로, 각 명함마다 큰 값을 가로, 작은 값을 세로로 정리해서 생각하면 된다.

즉, 각 명함을 다음 기준으로 통일한다.

큰 값 → 가로 후보
작은 값 → 세로 후보

모든 명함을 이렇게 정리한 뒤, 가로 후보 중 최댓값과 세로 후보 중 최댓값을 곱하면 필요한 지갑의 최소 넓이를 구할 수 있다.

핵심은 각 명함을 회전시켜도 된다는 점이다. 따라서 가로와 세로의 위치 자체보다, 두 값 중 큰 값과 작은 값을 분리하는 것이 중요하다.

처음 접근

처음에는 각 명함을 순회하면서 가로가 세로보다 작으면 두 값을 바꾸고, 가로 리스트 w와 세로 리스트 h에 값을 저장하는 방식으로 접근했다.

접근 방향 자체는 맞았다. 다만 처음 코드에서는 append() 사용 방식과 append()의 위치에서 문제가 있었다.

처음 코드에서 틀린 점

def solution(sizes):
    answer = 0
    w = []
    h = []
    for i in range(len(sizes)):    
        if sizes[i][0]<sizes[i][1]:
            sizes[i][0], sizes[i][1] = sizes[i][1], sizes[i][0]
            w = w.append(sizes[i][0])
            h = h.append(sizes[i][1])
    answer = max(w) * max(h)
    return answer

1. append()의 반환값을 다시 대입했다

처음 코드에서는 다음과 같이 작성했다.

w = w.append(sizes[i][0])
h = h.append(sizes[i][1])

 

 하지만 append()는 리스트에 값을 추가하는 메서드일 뿐, 수정된 리스트를 반환하지 않는다. append()의 반환값은 None이므로, 위처럼 작성하면 w와 h가 None으로 바뀔 수 있다.

잘못된 형태: w = w.append(value)
올바른 형태: w.append(value)

2. append()가 if문 안에 있었다

 처음에는 append()가 if문 안에 있어서, 회전이 필요한 명함만 리스트에 저장되었다. 하지만 이미 가로가 세로보다 큰 명함도 지갑 크기 계산에 반드시 포함되어야 한다.

 따라서 가로와 세로를 바꾸는 작업은 조건에 따라 수행하되, 리스트에 추가하는 작업은 모든 명함에 대해 실행되어야 한다.

필요하면 가로와 세로를 바꾼다. 그 다음에는 바꿨든 안 바꿨든 모든 명함의 값을 w와 h에 추가해야 한다.

개선 방향

 먼저 append()를 대입 없이 사용하도록 수정했다. 그 다음 w.append()와 h.append()의 위치를 if문 밖으로 이동했다.

1. 각 명함을 하나씩 확인한다.
2. 첫 번째 값이 두 번째 값보다 작으면 두 값을 바꾼다.
3. 바꿨든 안 바꿨든 큰 값을 w에 넣고, 작은 값을 h에 넣는다.
4. max(w) * max(h)로 최종 지갑 넓이를 구한다.

최종 풀이

def solution(sizes):
    answer = 0
    w = []
    h = []

    for i in range(len(sizes)):    
        if sizes[i][0] < sizes[i][1]:
            sizes[i][0], sizes[i][1] = sizes[i][1], sizes[i][0]       

        w.append(sizes[i][0])
        h.append(sizes[i][1])

    answer = max(w) * max(h)
    return answer

풀이 흐름

sizes[i][0]은 i번째 명함의 첫 번째 길이, sizes[i][1]은 두 번째 길이다. 두 값 중 첫 번째 값이 더 작다면 두 값을 교환해서 큰 값이 앞에 오도록 만들었다.

예: [30, 70] → [70, 30]

이렇게 정리하면 모든 명함에서 앞쪽 값은 큰 길이, 뒤쪽 값은 작은 길이가 된다. 그 다음 큰 길이들 중 최댓값과 작은 길이들 중 최댓값을 구해 곱하면 지갑의 최소 넓이를 구할 수 있다.

이번 풀이에서는 직접 값을 교환했지만, 같은 아이디어를 max()와 min()으로도 표현할 수 있다. 중요한 것은 각 명함마다 큰 값과 작은 값을 같은 기준으로 분리하는 것이다.

유사 유형 문제

명함 크기 리스트 sizes가 주어졌을 때, 각 명함을 회전할 수 있다고 가정하고 모든 명함을 담을 수 있는 최소 지갑의 둘레를 구하는 문제를 추가로 풀었다.

유사 문제도 핵심 구조는 동일했다. 각 명함에서 큰 값과 작은 값을 정리한 뒤, 필요한 지갑의 가로와 세로를 구했다. 다만 마지막 계산이 넓이가 아니라 둘레라는 점이 달랐다.

유사 문제 풀이

def solution(sizes):
    w = []
    h = []

    for i in range(len(sizes)):    
        if sizes[i][0] < sizes[i][1]:
            sizes[i][0], sizes[i][1] = sizes[i][1], sizes[i][0]       

        w.append(sizes[i][0])
        h.append(sizes[i][1])

    answer = max(w) * 2 + max(h) * 2
    return answer

원래 문제와 같은 점

두 문제 모두 2차원 리스트를 순회하면서 각 내부 리스트의 두 값을 비교하고, 필요하면 위치를 바꾸는 구조를 사용했다. 또한 정리된 가로 후보와 세로 후보를 각각 리스트에 저장하고 max()로 최종 크기를 계산했다.

핵심 문법은 2차원 리스트 인덱싱, 값 교환, append(), max() 사용이다.

원래 문제와 다른 점

원래 문제에서는 지갑의 넓이를 구했기 때문에 max(w) * max(h)를 사용했다. 유사 문제에서는 지갑의 둘레를 구했기 때문에 max(w) * 2 + max(h) * 2를 사용했다.

넓이 계산: max(w) * max(h)
둘레 계산: max(w) * 2 + max(h) * 2

다만 이번 유사 문제는 마지막 계산식만 바뀐 성격이 강했다. 다음부터는 단순히 조건식이나 계산식만 바꾸는 문제보다, 같은 핵심 문법을 다른 상황에서 다시 쓰는 문제로 연습할 예정이다.

핵심 정리

이번 풀이의 핵심은 각 명함의 두 길이를 비교해서 큰 값과 작은 값을 같은 기준으로 정리하는 것이다.

 명함은 회전할 수 있으므로 처음 주어진 가로와 세로를 그대로 사용할 필요가 없다. 각 명함에서 큰 값을 가로 후보로, 작은 값을 세로 후보로 모으면 모든 명함을 담을 수 있는 지갑 크기를 쉽게 계산할 수 있다.

 또한 append()는 값을 추가하는 동작만 수행하고 반환값은 None이므로, w = w.append(...)처럼 대입하면 안 된다. 리스트에 값을 추가할 때는 w.append(...)처럼 단독으로 사용해야 한다.

사용한 핵심 문법 정리

2차원 리스트 인덱싱

sizes[i][0], sizes[i][1]처럼 리스트 안의 리스트에 접근할 때 사용했다.

range(len(sizes))

sizes의 인덱스를 0부터 마지막까지 순회하기 위해 사용했다.

if 조건문

각 명함에서 첫 번째 값이 두 번째 값보다 작은지 확인하고, 필요한 경우 두 값을 교환했다.

값 교환

sizes[i][0], sizes[i][1] = sizes[i][1], sizes[i][0] 형태로 임시 변수 없이 두 값을 바꿨다.

append()

리스트에 값을 추가할 때 사용했다. append()는 반환값이 None이므로 대입해서 사용하면 안 된다.

max()

가로 후보 리스트와 세로 후보 리스트에서 각각 가장 큰 값을 찾기 위해 사용했다.

들여쓰기 위치

append()가 if문 안에 있으면 조건을 만족한 명함만 저장된다. 모든 명함을 저장하려면 append()를 if문 밖에 두어야 한다.

정리하면, 이 문제는 2차원 리스트를 순회하면서 각 내부 리스트의 값을 같은 기준으로 정렬한 뒤, 필요한 최댓값을 구하는 문제다. 비슷한 유형에서는 값 교환, 리스트 누적, 최댓값 계산 흐름을 다시 활용할 수 있다.