문제 설명
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.
| 명함 번호 | 가로 길이 | 세로 길이 |
|---|---|---|
| 1 | 60 | 50 |
| 2 | 30 | 70 |
| 3 | 60 | 30 |
| 4 | 80 | 40 |
가장 긴 가로 길이와 세로 길이가 각각 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 이하인 자연수입니다.
풀이
첫번째 풀이
def sortSize(card):
tempCard = []
if (card[1] > card[0]):
tempCard.append(card[1])
tempCard.append(card[0])
else:
tempCard.append(card[0])
tempCard.append(card[1])
return tempCard
def solution(sizes):
afterBig = []
afterSmall = []
for size in sizes:
afterBig.append(sortSize(size)[0])
afterSmall.append(sortSize(size)[1])
maxB = max(afterBig)
maxS = max(afterSmall)
answer = maxB *maxS
return answer처음에는 무식하게 하드코딩으로 확인하는 방법을 썼다. 우리가 구하고자 하는건 각각의 가로세로에서 최대 값의 길이이기 때문에, 일단 명함을 한 방향으로 (길이가 긴 쪽이 한쪽으로 오게) 정렬한 다음에 그 각각의 가로, 세로 길이에서 max 값을 찾아서 계산하는 방향으로 했다.
하지만, 코드를 읽다보니 너무 길었고, 필요 없는 부분들이 많아서 내 나름대로 조금 고쳐보았다 그렇게 작성한게 두번째 코드이다
두번째 풀이
def solution(sizes):
afterSort =[[],[]]
for size in sizes :
afterSort[0].append(max(size))
afterSort[1].append(min(size))
answer = max(afterSort[0])*max(afterSort[1])
return answer아까보다 훨씬 깔끔해졌고, auxiliary function이 없어져서 조금 더 깔끔한 느낌으로 작성할 수 있었다.
다른사람 풀이
첫번째 풀이
def solution(sizes):
return max(max(x) for x in sizes) * max(min(x) for x in sizes)항상.. 한줄짜리 코드 보면서 신기하고.. 언젠가 나도 저렇게 할 수 있을까 싶고.. 그렇다.. 코드 흐름 자체는 내 코드랑 크게 다르지 않은데 한줄만에 끝나는게 너무 대단해보임
두번째 풀이
solution = lambda sizes: max(sum(sizes, [])) * max(min(size) for size in sizes)lambda를 이용한 풀이도 항상 신기하다.. 람다 이해했다고 생각했는데 이런거 보면 또 아닌거같기도 하고.. 내가 사용을 잘 못하는 것 같기도 하고 그렇다. 자주 보면 친숙해지고 늘겠지!
세번째 풀이
def solution(sizes):
import heapq
mq_w, mq_h = [], []
for size in sizes:
w, h = size[0], size[1]
if w < h: w, h = h, w
heapq.heappush(mq_w, -w)
heapq.heappush(mq_h, -h)
return mq_w[0] * mq_h[0]heapq를 이용한 풀이도 생각보다 많이보여서 신기했다.
heapq는 priority queue라고도 하는데, binary tree 개념을 사용해서 항상 root node 가 제일 작은 값을 갖는다. 이 속성을 이용해서 일부러 heappush 할때 주어진 숫자를 negate해서 push 하신걸 보고 감탄했다. 이렇게도 쓸 수 있구나..
