URL : https://programmers.co.kr/learn/courses/30/lessons/86491
문제 설명
- 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
- 아래 표는 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 이하인 자연수입니다.
문제풀이
- 명함의 가로세로를 고려해야해서 어려워 보이지만, 사실 문제의 명함에서는 회전이 가능하기 때문에 가로와 세로가 딱 정해진것은 아니다.
- 따라서 각 명함의 사이즈로 주어진 가로세로 크기에서 작은것은 가로, 큰것은 세로로 정렬한뒤 전체 명함 사이즈 중 가장큰 가로와 가장큰 세로를 곱해주기만 하면 된다.
- 1차 솔루션은 sizes에 있는 모든 원소 size를 for문을 돌며 정렬하고 가로의 가장큰값과 세로의 가장큰값을 비교하며 갱신하여 마지막에 곱해주는 방식을 사용했다
- 위 방법은 for문은 1번이나 sorted를 sizes의 원소만큼 해야해서 비효율적이라 생각했다.
- 2차 솔루션은 리스트컴프리헹션을 사용하여 가로와 세로의 사이즈를 각각 w_, h_라는 리스트에 저장 후 가장 큰값을 곱했다.
- 코드자체는 줄어보이나, for문도 가로와 세로로 각각 1번씩, 그리고 sorted로 각 sizes의 원소갯수만큼 하기 때문에 많이 비효율적이다.
- 3차 솔루션은 리스트컴프리행션을 사용하여 주어진 명함의 가로와 세로의 size를 정렬 한뒤 zip 함수를 이용해 가로와 세로의 사이즈를 다시 묶어주고 가로와 세로의 max값을 곱해주었다.
- 1차 솔루션에 비해 코드도 간결해졌고 for문도 1번만 돌아서 나름 효율적이나, sorted를 어쩔수 없이 sizes의 원소만큼 해줘야 한다.
- 그래도 1차, 2차 솔루션 보다는 효율적이라 생각해서 최종 제출을 하였다.
- sorted도 2차원 list를 input으로 받고 for문을 사용하지 않고 원소별로 비교해서 sorted를 하는 방법을 알게된다면 더 효율적이 될것같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 1차 솔루션
def solution(sizes):
w_max = 0
h_max = 0
for size in sizes:
sorted_size = sorted(size)
if w_max < sorted_size[0]:
w_max = sorted_size[0]
if h_max < sorted_size[1]:
h_max = sorted_size[1]
return w_max * h_max
1
2
sizes = [[60, 50], [30, 70], [60, 30], [80, 40]]
solution(sizes)
1
4000
1
2
sizes = [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]
solution(sizes)
1
120
1
2
sizes = [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]
solution(sizes)
1
133
1
2
3
4
5
# 2차 솔루션
def solution(sizes):
w_ = [sorted(size)[0] for size in sizes]
h_ = [sorted(size)[1] for size in sizes]
return max(w_) * max(h_)
1
2
sizes = [[60, 50], [30, 70], [60, 30], [80, 40]]
solution(sizes)
1
4000
1
2
sizes = [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]
solution(sizes)
1
120
1
2
sizes = [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]
solution(sizes)
1
133
1
2
3
4
5
6
7
# 3차 솔루션
def solution(sizes):
sorted_sizes = [sorted(size) for size in sizes]
new_sizes = list(zip(*sorted_sizes))
# new_sizes[0] : 가로 길이 모음
# new_sizes[1] : 세로 길이 모음
return max(new_sizes[0]) * max(new_sizes[1])
1
2
sizes = [[60, 50], [30, 70], [60, 30], [80, 40]]
solution(sizes)
1
4000
1
2
sizes = [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]
solution(sizes)
1
120
1
2
sizes = [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]
solution(sizes)
1
133