핵심을 파악하는 탐욕법 알고리즘

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/86491?language=python3 

코딩테스트 연습 - 최소직사각형

 

명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다.

 

다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다.

 

이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

 

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

 

 

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에

 

80(가로) * 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다.

 

하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) * 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다.

 

이 때의 지갑 크기는 4000(=80*50)입니다.

 

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다.

 

모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return하도록 solution 함수를 완성해주세요.

 

 

2. 제한사항

 

sizes의 길이는 1이상 10000이하입니다.

 

sizes의 원소는 [w,h]입니다.

 

w는 명함의 가로 길이를 나타냅니다.

 

h는 명함의 세로 길이를 나타냅니다.

 

w와 h는 1이상 1000이하인 자연수입니다.

 

 

3. 예시

 

 

4. 나의 풀이

 

명함들이 가로 w, 세로 h로 되어 있을텐데 어떤 것은 w<h이고 어떤 것은 w>h로 되어있을 것임

 

문제에서 w<h로 된 것을 w>h로 바꿔서 수납해도 된다고 했음

 

문제 설명을 보면 가로의 길이 max * 세로의 길이 max인 명함 지갑을 만들어야 한다는 것을 알 수 있음

 

그래야 모든 명함을 담을 수 있기 때문에

 

가로의 길이 리스트에서 max를 구하고 세로의 길이 리스트에서 max를 구할건데

 

가로, 세로의 max를 구하기 때문에 두 값의 곱이 최소일려면 어느 한쪽은 충분히 작게 만들어야함

 

만약 각 명함마다 가로 길이와 세로 길이 중 큰 값을 가로 길이쪽에 몰아넣으면,

 

그러니까 가로<세로이면 눕혀서 가로>세로로 바꾸라는 이야기

 

그렇다면  세로의 길이 max를 최소로 만들 수 있음

 

def solution(sized):
    
    answer = 1
    
    new_size = []
    
    for w,h in sizes:
        
        if w < h:
            
            new_size.append([h,w])
            
        else:
        
            new_size.append([w,h])

 

그래서 빈 리스트 하나를 만들고 가로의 길이가 큰 경우는 그대로 넣고

 

세로의 길이가 큰 경우는 가로>세로로 바꿔서 넣는다

 

for column in zip(*new_size):
    
    answer = answer * max(column)
    
return answer

 

다음 zip(*new_size)를 하면 가로의 길이를 모은 컬럼 리스트와 세로의 길이를 모은 컬럼 리스트를 가져오는데

 

그러니까 new_size = [ [w1,h1] , [w2,h2], ... , [wn,hn] ] 이런식으로 되어있을텐데

 

zip(*new_size)하면 zip([w1,h1] , [w2,h2], ... , [wn,hn] )이 될 것이다

 

그래서 column에는 가로의 길이 리스트인 [w1,w2,w3,....,wn]과 세로의 길이 리스트인 [h1,h2,...,hn]이 들어간다

 

answer=1이니까 max(column)을 차례대로 곱하면 가로중 최댓값과 세로중 최댓값이 곱해지면서

 

가로에는 최댓값들만 몰아넣었고

 

세로에는 최솟값들만 몰아넣어서

 

전체 크기가 최소인 명함지갑을 얻는다

 

 

5. 다른 풀이

 

좋아요를 많이 받은 풀이들

 

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

 

max 함수 내에 max(x) for x in sizes를 넣은게 특이한데

 

max(x) for x in sizes를 하면 sizes에서 for문을 돌아서 만나는 원소마다 [가로,세로] 중에서 최댓값을 뽑아 generator로 만든다

 

 

print로 찍어보면 generator가 나오고

 

list로 씌운다음에 print로 찍으면 어떻게 생긴건지 보여줘

 

max(min(x) for x in sizes)도 마찬가지

 

결국엔 내가 사용한 알고리즘인 최댓값 가로와 최솟값 세로의 곱을 사용했는데 한줄로 짧게 만든거임

 

다른 풀이를 또 보면

 

def solution(sizes):
    
    row = 0
    
    col = 0
    
    for a,b in sizes:
        
        if a<b:
            
            a,b = b,a
            
        row = max(row,a)
        col = max(col,b)
        
    return row * col

 

 

나랑 똑같은 알고리즘이긴 한데 하나의 for문으로 끝냄

 

row, col을 0으로 초기화한다음에

 

sizes에서 가로,세로를 뽑고

 

가로<세로이면 세로,가로가 되도록 배열한 다음

 

row와 col에 max값을 갱신해나가서

 

for문 하나 끝나면 바로 row*col로 return하도록

 

6. 되돌아보기

 

코딩에서 아쉬운 부분 있을지 몰라도

 

문제 풀이를 위한 핵심 알고리즘을 잘 파악했다

 

max(a) * max(b)가 최소가 되도록 만들어야하는데

 

리스트 a에서 최댓값을 뽑고 리스트 b에서 최댓값을 뽑을건데

 

결국엔 어느 한쪽을 충분히 작게 만들어야 max(a)*max(b)가 최소가 될거임