Posts 8Week 최소직사각형 [Python]
Post
Cancel

8Week 최소직사각형 [Python]

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

문제 설명

  • 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
  • 아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.
명함 번호가로 길이세로 길이
16050
23070
36030
48040
  • 가장 긴 가로 길이와 세로 길이가 각각 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
This post is licensed under CC BY 4.0 by the author.

7Week 입실 퇴실 [Python]

n^2 배열 자르기 [Python]

Comments powered by Disqus.