[2024] Day1. 455. Assign Cookies

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 1일 (월)
Leetcode daily problem

455. Assign Cookies

https://leetcode.com/problems/assign-cookies/?envType=daily-question&envId=2024-01-01

Problem

• 아이들에게 쿠키를 할당하는데, 각 아이는 만족도가 다르게 주어진 쿠키를 받는다. 최대한 많은 아이들에게 만족도를 높이는 쿠키를 할당하는 것이다.
• 문제에서 주어지는 두 가지 배열은 아이들의 만족도 g와 쿠키의 크기로 s로 이다. 만족도 배열 g는 아이들이 받고자 하는 만족도이며, 쿠키 배열 s는 사용 가능한 쿠키의 크기를 나타낸다.
  각 아이는 자신의 만족도 이상의 크기를 가진 쿠키를 받으면 만족한다.

Solution

그리디(Greedy) 알고리즘 사용

(1) 아이들의 만족도와 쿠키의 크기를 오름차순으로 정렬한다.
(2) 만족도가 가장 낮은 아이부터 시작해 그 아이에게 만족도를 넘는 가장 작은 쿠키를 할당한다.
(3) 할당한 후에는 다음 아이로 넘어가고, 할당할 쿠키도 다음 크기로 넘어간다.
(4) 만약 해당 크기의 쿠키로도 아이에게 만족도를 주지 못한다면, 쿠키의 크기를 키워가며 계속 시도한다.

=> 그리디 알고리즘은 각 단계에서 현재 상태에 가장 최적인 선택을 하는 방식으로 동작한다.
해당 문제에서는 어린이에게 할당되는 과자의 크기가 어린이의 만족에 영향을 미치고,
만족도가 높은 어린이에게 큰 크기의 과자를 주어야 한다.
즉, 각 단계에서 현재 상태의 최적 선택이 전체 최적해로 이어져야 하는데, 각 단계에서 현재 상태에 가장 최적의 선택을 해야 하므로, 만족도가 낮은 어린이에게는 크기가 작은 과자를 줘서 최대한 많은 어린이에게 과자를 할당해야 하므로 그리디 알고리즘으 활용하는 것이 좋다.

Code

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i, j = 0,0
        ans = 0

        while i<len(g) and j<len(s):
            if g[i] <= s[j]:
                ans+=1
                i+=1
            j+=1
        
        return ans

Complexicity

시간 복잡도

어린이 만족도와 쿠키 배열의 크기를 정렬하므로 O(nlogn)
while loop로 만족도, 어린이 쿠키를 한번 순회하므로 O(n) 이다.
전체 시간복잡도는 O(nlogn) + O(n) = O(nlogn) 이다.

공간 복잡도
주어진 배열에서만 sort하므로 o(1)의 공간복잡도를 가진다.

---

다른 Solution

Neetcode 강의를 봤는데 이중 while문을 써서 풀었다.
둘다 같은 시간복잡도 및 공간복잡도를 가진다.

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i=j=0

        while i<len(g):
            while j<len(s) and g[i] > s[j]:
                j +=1
            if j == len(s):
                break
            i+=1
            j+=1
        return i