[Programmers] 최소직사각형

최소직사각형

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

 

문제 정의

다양한 모양/크기의 명함을 모두 수납할 수 있는 지갑을 만들어야 한다. 모든 명함의 가로 길이와 세로 길이가 2차원 배열(sizes)로 주어지면 모든 명함을 수납할 수 있는 가장 작은 사이즈의 지갑을 return 해야 한다.

주의할 점: 지갑을 가로 또는 세로로 눕혀서 수납할 수도 있음. → 지갑의 가로와 세로 길이를 바꿔 계산할 수 있음.

 

접근 방법

---

이 문제는 단순히 (가로의 최댓값) * (세로의 최댓값) 을 구해서 지갑의 크기를 구하는 문제가 아니다.

모든 명함의 가로 길이를 포함하면서 세로 길이도 충족하게 끔 지갑의 사이즈를 정해야 한다.

이 문제의 핵심은 지갑을 가로로 눕힐 수 있다는 점이다. 이 점을 고려해 지갑의 (가로, 세로)를 정하면 된다.

1. 첫번재 접근

• 구현이라고 생각하고 명함을 포함할 수 있는 모든 지갑의 크기를 다 구하고, 그 중에서 가장 작은 사이즈의 지갑을 리턴하려고 했다. → 잘못된 접근

1. 두번째 접근

• 첫번째 접근의 풀이가 잘못됐음을 알고 모범답안을 살펴보았다.
• 지갑의 가로길이는 명함의 모든 가로를 포함하면되고, 지갑의 세로 길이는 명함의 모든 세로 길이를 포함하면 된다는 사실을 다시 본다면?
• 👉 명함의(가로-세로) 중 큰 것은 가로(또는 세로)로, 작은 것은 세로(또는 가로)로 설정하고, 이 둘의 곱을 구하면 된다.

 

문제 해설

---

• (가로, 세로) 중 큰 값은 가로로, 작은 값은 세로로 취급한다.
• 가로 리스트 중 가장 큰 값 * 세로 리스트 중 가장 큰 값 을 구하면 된다.

 

풀이

---

1. 올바른 풀이

# 모든 명함을 수납할 수 있는 가장 작은 지갑
def solution(sizes):
    answer = 0
    max_w, max_h = [], []
    
    for s in sizes:
        if s[0] > s[1]:
            max_w.append(s[0])
            max_h.append(s[1])
        else:
            max_h.append(s[0])
            max_w.append(s[1])
    
    answer = max(max_w) * max(max_h)
    
    return answer

 

2. 첫번째 접근(잘못된 풀이)

• 일단 주어진 sizes 에서 가로 최댓값 * 세로 최댓값을 구하고
• 큰 값을 기준으로 가로와 세로의 위치를 하나씩 바꿔보면서 구해진 지갑 사이즈와 비교했다.
• 구해진 지갑 사이즈 > 가로-세로를 바꿔서 계산된 사이즈이면 → 지갑 사이즈를 업데이트 했다.
• 가로-세로가 변경될 수 있는 숫자가 꼭 큰 숫자만은 아니었다. 나의 착각이었다.

# 모든 명함을 수납할 수 있는 가장 작은 지갑
import copy 

def max_size(size_list):
    max_width = size_list[0][0]
    max_height = size_list[0][1]
    
    for s in size_list:
        max_width = max(max_width, s[0])
        max_height = max(max_height, s[1])
        
    return max_width, max_height
    
def solution(sizes):
    answer = 0
    # 일단 가로 max, 세로 max를 구해서 지갑 크기를 구한다.
    
    max_w, max_h = max_size(sizes)
    answer = max_w * max_h  # 가장 큰 가로, 세로 길이일 때 지갑 크기
    
    # 가로를 세로로 바꿔보기
    tmp_sizes = copy.deepcopy(sizes)
    for s in tmp_sizes:
        if max_w == s[0]:
            tmp = s[1]
            s[1] = s[0]
            s[0] = tmp
            
    tmp_mw, tmp_mh = max_size(tmp_sizes)
    answer = min(answer, (tmp_mw*tmp_mh))
    
    # 세로를 가로로 바꿔보기
    tmp_sizes = copy.deepcopy(sizes)
    print(tmp_sizes)
    for s in tmp_sizes:
        if max_h == s[1]:
            tmp = s[0]
            s[0] = s[1]
            s[1] = tmp
            
    tmp_mw, tmp_mh = max_size(tmp_sizes)

    answer = min(answer, (tmp_mw*tmp_mh))
    
        
    return answer

 

 

정리

---

• 구현이라고 해서 하나씩 다 구해보는 문제라고 생각하고 접근했는데 그게 아니었다.
• 아이디어가 필요한 문제였다.
• 시간 복잡도는 sizes만큼 돌면되므로, $O(N)$