[문제 출처 : Codechef] 쿠키를 만드는 공장에서 다양한 무게의 N개의 쿠키들을 만들었습니다. 그리고 쿠키를 하나씩 포장할 상자들 또한 N개를 만들었습니다. 하지만 안타깝게도 매니저가 그렇게 현명하지 못해서 상자가 포장할 수 있는 쿠키의 무게에 한계가 있다고 합니다 ㅠㅠ N개의 쿠키들의 무게와, N개의 상자들이 포장할 수 있는 한계 무게가 주어졌을 때, 최대로 포장할 수 있는 쿠키의 수를 구해주세요.
예를 들면, 쿠키의 무게가 [10, 30, 20]으로 주어졌고, 상자가 담을 수 있는 한계 무게가 [30, 10, 20]으로 주어졌을 때, 우리는 최대 3개의 쿠키 모두를 각각의 상자에 담을 수 있습니다. (10을 10, 20을 20, 30을 30에 할당했을 경우) 어떻게 이 최대 쿠키 개수를 찾을 수 있을까요?
정말 무식하게 푸는 방법은, 모든 경우의 수를 다 대입해서 최대의 개수를 찾는 것입니다. 이런 경우, 각 쿠키를 하나의 상자에 모두 대입시켜 봐야 하기 때문에, \[O(n\times(n-1)\times … \times 2 \times 1) = O(n!)\]이라는 무시무시한 경우의 수를 검사해 봐야 합니다. 그럼 어떻게 하면 빠르고 효율적이게 최대의 개수를 파악할 수 있을까요?
방법은 바로 Sorting을 활용하는 것입니다! 각각 쿠키들의 무게와 상자의 한계 무게를 오름차순으로 정렬했다고 가정해 봅시다. 그러고 나면 가장 작은 무게부터 들어갈 수 있는 가장 작은 상자를 찾기 시작합니다. 어차피 상자 하나에 하나의 쿠키만 넣을 수 있기 때문에, 이런 식으로 넣는 경우 우리는 바로 넣을 수 있는 최대 쿠키의 개수를 구할 수 있게 됩니다. 이 때는 Sorting하는 데 필요한 $O(n\log n)$과 각각 넣을 수 있는지 파악하기 위한 $O(n)$만 필요하기 때문에 팩토리얼과는 비교도 할 수 없을 정도로 빠르게 계산하게 됩니다.
이제 코드를 살펴보면,
def maxNumPack(w, l):
#먼저 정렬을 하구요,
w.sort()
l.sort()
count = 0
ind = 0
for weight in w: #작은 무게부터 꺼내보고,
while ind < len(l) and weight > l[ind]: #limit이 현재 무게보다 더 큰 것이 나올때까지 다음 limit으로 옮깁니다.
ind += 1
if ind == len(l): #만약 상자를 다 사용했으면 더 담을 수 없으니 반복문을 종료합니다.
break
# 상자가 남아있으면, 현재 물건을 담고 다음 물건을 살펴봅니다.
count += 1
ind += 1
return count
>>> print maxNumPack([10, 30, 20], [30, 10, 20])
3
>>> print maxNumPack([9, 7, 16, 4, 8], [8, 3, 14, 10, 10])
4결과값이 잘 나옴을 확인하실 수 있죠? 은근히 정렬을 이용한 빠른 해결책들이 많기 때문에 알고리즘에 잘 적용할 수 있도록 많이 익숙해지시길 바랍니다 :)