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

프로그래머스

def solution(sizes):
    
    sizes = [sorted(x,reverse=True) for x in sizes]  # [[60, 50], [70, 30], [60, 30], [80, 40]]
    
    widths = [x[0] for x in sizes] # [60, 70, 60, 80]
    heights = [x[1] for x in sizes] # [50, 30, 30, 40]
    
    return max(widths)*max(heights)

이번 문제는 주어진 명함들의 가로와 세로길이가 주어졌을 때, 명함을 가로나 세로로 회전할 수 있다는 가정하에 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때 필요한 지갑의 크기(넓이)를 구하는 문제이다.

 

처음엔 완전탐색으로 풀이했었는데, sizes의 길이가 최대 10,000이라서 시간초과가 발생하게 되었다.

따라서 다른 사람의 풀이를 보면서 많은 힌트를 얻었다. 모든 가로와 세로의 경우의 수를 세어보는 것이 아니라 가로와 세로 중 더 긴 길이를 가로로, 더 짧은 길이를 세로로 고정시킨 후 그 길이들 중 가장 긴 값(max)의 곱이 정답이 된다.

 

배운 점 및 느낀 점

1. 최소와 최대를 구하기 번거로운 상황이라면, 한 가지 값을 고정시킨 뒤에 풀어보도록 하자.
2. 프로그래머스에서는 히든 케이스는 잘 주어지지 않으므로, 문제를 풀이할 때 예외나 시간복잡도를 먼저 잘 확인하도록 하자.