[TIL 2024. 03. 26] 최소 직사각형 | 2차원 리스트에서 요소 추출하기

최소 직사각형

프로그래머스

 

어떤 알고리즘을 사용하지?

제한사항에 따르면 문제에서 주어지는 2차원 리스트인 sizes의 길이는 1~10,000 사이이다.

해당 문제는 이렇게 input값이 작고, 모든 명함이 수납되는 "가장 작은 지갑"을 return하는 함수를 작성하라고 한다.

 

이럴 때 사용하기 좋은 알고리즘이 바로 "완전탐색(Brute Force)"이다

완전탐색의 특성상 모든 경우의 수를 탐색하므로, 문제의 결과값을 얻을 수 있는 가장 확실하고 기초적인 방법이다. 하지만 input이 많은 경우에는 시간 복잡도의 제한으로 완탐을 이용하기 어려운 경우도 있다

 

하지만 해당 문제는 input의 수가 1만 정도로 적기 때문에 반복문과 조건문을 사용하는 완탐을 이용할 수 있다

 

 핵심적인 부분은 어디일까?

문제에서는 "명함들을 적절히 회전시켜 겹칠 수 있다"고 명시하고 있다.

즉, input이 다음과 같이 [w,h] 형식으로 주어질 때 가로가 더 긴 경우와 새로가 더 긴 경우가 혼재해 있다.

 

하지만 문제에서는 이들을 회전시켜 가로 세로를 바꿀 수 있다고 했으므로, 문제를 풀 때는 각각의 명함에서 긴 쪽과 짧은 쪽을 모을 변수(w와 h)를 분리하는 게 중요하다. 그 후에 각 변수의 최댓값을 서로 곱하면 모든 명함을 넣을 수 있는 "가장 작은" 지갑의 크기를 return할 수 있다 

[가로>세로], [가로<세로]가 혼재해 있음 (출처:프로그래머스)

 

 

 

답안 코드 

def solution(sizes):
    w = []      #긴 쪽과 짧은 쪽으로 나눠담을 변수 준비
    h = []  
    for size in sizes:
        w.append(max(size))     #max,min으로 구분
        h.append(min(size))
    return max(w)*max(h)


def solution(sizes):
    num1, num2 = [], []
    for size in sizes:
        size.sort()     #sort()로 정렬해서 구분
        num1.append(size[0])
        num2.append(size[1])
    return max(num1)*max(num2)

 

이 문제는 2차원의 명함이 대상이라 구분해서 나눠담는 변수가 2개 뿐이지만, 만약 input이 [60,30,50]과 같이 3개 이상이 된다면 max,min으로 구분하는 것보다는 sort()를 사용하고 index를 사용하는 게 더 좋을 수도 있겠다..

 

아래와 같이 코드를 작성한 분들도 계셨다.

def solution(sizes):
    return max(max(x) for x in sizes) * max(min(x) for x in sizes)

 

---

2차원 리스트에서 특정 열 추출하기

위 문제에서 삽질하다 보니 2차원 리스트에서 특정 열을 추출하는 방법도 찾아보았다

언젠가는 써먹을테니 찾아본 내용을 정리해보겠다

 

sizes = [[60, 50], [30, 70], [60,30], [80,40]]

 

다음과 같이 2차원 리스트가 주어진 경우, 같은 열끼리 리스트로 묶어서 출력하는 법은 다음의 4가지이다.

현실적으로는 방법2, 방법3을 가장 많이 이용하게 될 것 같다

 

 

방법1. 변수 a,b에 unpack해서 할당

def solution(sizes):
    num1, num2 = [], []
    for a,b in sizes:
        num1.append(a)
        num2.append(b)
    print(num1)
    print(num2)

# [60, 30, 60, 80]
# [50, 70, 30, 40]

 

---

방법2. inline for loop

def solution(sizes):
    num1 = ([i[0] for i in sizes])
    num2 = ([i[1] for i in sizes])
    print(num1)
    print(num2)

# [60, 30, 60, 80]
# [50, 70, 30, 40]

 

---

방법3. zip 이용

def solution(sizes):
    num1 = list(zip(*sizes))[0] #반드시 unpack해줘야.
    num2 = list(zip(*sizes))[1]
    print(num1)
    print(num2)

# (60, 30, 60, 80)
# (50, 70, 30, 40)

 

---

방법4. numpy 모듈 이용

import numpy as np

def solution(sizes):
    num1 = np.array(sizes).T[0]
    num2 = np.array(sizes).T[1]
    print(num1)
    print(num2)

# [60 30 60 80]
# [50 70 30 40]

 

 

 

참고자료

https://maktubi.tistory.com/93

https://hongjw1938.tistory.com/78