• 코테 시리즈에 올리려다가 프로그래머스 알고리즘 고득점 kit만 따로 정리하는 게 나을 거 같아서 정리
• 근데 이렇게 한땀한땀 문제 정리하면 문제 정리하는 시간이 더 들 거 같은데 어카지

완전탐색 - 최소직사각형 문제풀이 리뷰

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

1. 문제 요약 & 내 아이디어

문제

• n개의 명함의 가로(w), 세로(h)의 정보를 알려 주는 2차원 배열 sizes를 매개변수로 줌
• n개의 명함이 모두 들어갈 수 있는 지갑 크기의 최솟값을 구하라
• 명함을 눕혀서 수납하는 것도 가능

아이디어

• 모든 명함을 돌릴 수 있으니, 각 명함을 짧은 변/긴 변으로 정렬하고 나면
• 짧은 변 중 가장 큰 것 ⇒ 최소 너버
• 긴 변 중 가장 큰 것 ⇒ 최소 높이
• 지갑 크기 = max(짧은 변) * max(긴 변)

2. 처음에 틀린 이유 (디버깅 과정)

• 파이썬도 코테도 2주만에 푸는 거라 문제 설계는 되는데 문법이 기억이 안 남(변명 맞음)

lst_w = []
lst_h = []

for _ in sizes:
    lst_w.append(sizes[0])
    lst_h.append(sizes[1])
  
 # 내 의도: sizes를 돌면서 안의 [w, h] 쌍 중 w가 lst_w에,
 # h가 lst_h에 들어가길 바람
 # 실제 코드: sizes의 길이 만큼 sizes[0]과 sizes[1]를 넣겠다는 의미

추측한 문제점 3가지

1. 2차원 배열 탐색 실패 ⇒ sizes[0] 은 첫 번째 명함이며, 루프에서 계속 그 값만 참조 ⇒ 명함 전체 순회 실패
2. list원소가 int가 아닌 string으로 인식 ⇒ map(Int, lst) 없이 max(lst) 했을 경우 문자열의 max값을 구할 것
3. sort, map 문법 까먹음

3. 핵심 개념 정리

• 2차원 배열 탐색
  • for size in sizes: 각각 [w, h] 쌍을 꺼내겠다
  • for w, h in sizes: 언팩 가능 ≤ 근데 나는 얘가 더 직관적이라 문제 풀 때 편한 거 같음…
• 각 명함을 오름차순 정렬하는 방법
• sizes,sort() ⇒ 전체 명함의 순서 정렬
• map(sorted, sizes) or w h = sorted([w, h]) ⇒ 명함 개별 정렬
• 왜 완전탐색 분류인가? 이 문제에서 모든 명함을 하나하나 전부 순회하며 회전 가능한지 확인하는 전략이 들어가 있기 때문.
  • 완전탐색이란? → 가능한 모든 경우의 수를 시도해보는 방식.
  • 이 문제는 각 명함에 대해 "어떤 방향이 최적인지"를 직접 확인함.
  • 따라서 복잡한 백트래킹이나 DFS는 아니지만, 분류상 완전탐색으로 들어간다.

4. 정답 코드 & 핵심 로직

#근데 난 통으로 복붙했는데 why 쪼개져서 올라감?

def solution(sizes):
lst_w = []
lst_h = []

• 짧은 변을 lst_w에, 큰 변을 lst_h에 넣어서 max값을 찾기 위한 리스트

for w, h in sizes:
    w, h = sorted([w, h])     # 짧은 쪽을 w, 긴 쪽을 h로 맞춤
    lst_w.append(w)
    lst_h.append(h)

return max(lst_w) * max(lst_h)

🔑 핵심 포인트

• 각 명함을 [작은 쪽, 큰 쪽]으로 정렬
• 짧은 변 중 최대, 긴 변 중 최대 → 지갑 크기