99클럽 코테 스터디 39일차 TIL (Assign Cookies) - LeetCode

말하는 감자·2024년 8월 29일

99클럽 99클럽3기 greedy algorithm leetcode python 그리디 정렬 코딩테스트 코딩테스트 준비 파이썬 향해99

99클럽 3기

목록 보기

39/42

오늘은 99클럽 코테 스터디 39일차 입니다.

오늘 문제는 그리디 알고리즘 유형의 문제입니다!

1. 오늘의 학습 키워드

그리디

2. 문제: 455. Assign Cookies

단계: Easy
주제: Array, Two Pointers, Greedy, Sorting
출처: https://leetcode.com/problems/assign-cookies/

455. Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

Constraints:

1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

3. 나의 풀이

문제 접근 방식

이 문제는 그리디 알고리즘을 활용하여 해결할 수 있습니다. 그리디 알고리즘은 매 순간 최선의 선택을 하여 전체 문제를 해결하는 전략입니다. 이 문제에서는 아이들의 만족도를 최대화하는 것이 목표이므로, 가능한 한 작은 쿠키로 더 많은 아이들을 만족시킬 수 있도록 전략을 세워야 합니다.

아이와 쿠키의 배열을 오름차순으로 정렬한 후, 가장 작은 쿠키부터 시작하여 아이들의 만족도를 채워줍니다. 만족도를 채워줄 수 있는 아이가 있다면, 해당 아이에게 쿠키를 주고 다음 아이로 넘어갑니다. 그렇지 않다면, 더 큰 쿠키를 찾아서 해당 아이를 만족시킬 수 있도록 합니다.

코드 설명

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        # 아이 1명당 1개의 쿠키를 줄 수 있음.
        # g[i]는 아이i마다 만족할 수 있는 최소 쿠키 크기
        # 각 쿠키j의 크기는 s[j]
        # 만약 s[j] >= g[i]라면, 쿠키 j를 아이 i에게 줄 수 있음, 아이는 만족
        # return : 만족한 아이들의 수를 최대화 하는 것.
        # 만족도가 낮은 아이에게 작은 쿠키를 주는것, 그래서 만족할 수 있는 아이를 최대화 하기

        g.sort()  # 아이들의 욕심 요소를 오름차순으로 정렬
        s.sort()  # 쿠키의 크기를 오름차순으로 정렬
        i = 0  # 만족시킨 아이들의 수를 셀 인덱스

        # 쿠키를 하나씩 검사하며, 아이들의 만족도를 확인
        for k in s:
            if k >= g[i]:  # 쿠키가 해당 아이를 만족시킬 수 있는 경우
                i += 1  # 아이를 만족시켰으므로, 다음 아이로 넘어감
            if i == len(g):  # 모든 아이를 만족시켰다면 중지
                break
        return i  # 만족한 아이들의 수를 반환

코드 동작 방식

정렬: 먼저 아이들의 욕심 요소와 쿠키의 크기를 각각 오름차순으로 정렬합니다. 이렇게 하면, 작은 쿠키로 작은 욕심을 가진 아이부터 만족시킬 수 있습니다.
포인터 활용: i라는 포인터를 사용하여 만족한 아이들의 수를 추적합니다. 쿠키 배열을 순회하면서, 현재 쿠키가 현재 아이를 만족시킬 수 있는지 검사합니다.
조건문 활용: 만약 현재 쿠키가 아이의 욕심 요소를 만족시킬 수 있다면, 아이를 만족시켰다는 의미로 i를 증가시킵니다. 만약 모든 아이가 만족되었다면 더 이상의 검사가 필요 없으므로 루프를 중지합니다.
결과 반환: 루프가 끝난 후 i는 만족한 아이들의 수를 나타내며, 최종적으로 이를 반환합니다.

이 코드는 그리디 알고리즘을 잘 활용하여, 최선의 선택을 통해 문제를 효율적으로 해결합니다. 시간 복잡도는 $O(n \log n)$ 으로, 이 문제를 해결하는 데 필요한 최선의 시간 복잡도를 가집니다.

결과

https://leetcode.com/problems/assign-cookies/submissions/1371899834

속도가 빠른 편이 아닌걸로 나오지만, 제일 빠른 코드를 봐도 시간복잡도가 $O(n \log n)$ 인 것은 동일합니다. 아무래도 현재 내 코드를 처리하는 상황에서 네트워크쪽에서 오버헤드가 발생한 것으로 보입니다.

마무리

이번 문제는 그리디 알고리즘을 사용하여 해결할 수 있는 문제로, 욕심 요소와 쿠키 크기를 정렬한 후 작은 것부터 하나씩 매칭해가는 간단한 접근 방식을 적용했습니다. 이 과정에서 가장 중요한 것은 최선의 선택을 반복하여 문제를 해결하는 그리디 알고리즘의 특성을 잘 이해하는 것이었습니다.

시간 복잡도 측면에서 이 문제는 주어진 상황에서 최선의 성능을 발휘할 수 있는 $O(n \log n)$ 정렬 기반 접근법이었습니다. 실제로 문제를 풀면서, 가장 최적화된 코드라도 정렬 단계에서의 시간 복잡도 한계로 인해, 이보다 더 빠른 시간 복잡도를 가진 방법은 없다는 것을 확인할 수 있었습니다.