[LeetCode#455] Assign Cookies

❒ Description

---

레벨	Easy
날짜	2024.09.19 (목)
제목	Assign Cookies
링크	https://leetcode.com/problems/assign-cookies/description/
자료구조	배열
알고리즘	그리디
시간 복잡도	O(NlogN)

 

 

 

 

 

❒ 문제 분석

---

우선 각 배열의 의미를 잘 이해해야 한다.

• g 배열 : i번 째 아이들를 만족시킬 수 있는 쿠키의 크기들의 집합
• i 배열 : 각 쿠키의 크기를 나타낸 집합

예를 들어 g = {1, 2, 3}, s = {1, 1} 이라면 최대 1명의 아이만 만족할 수 있다.

• s[1]은 g[1]을 만족시킬 수 있다.
• s[2]은 g[2]을 만족시킬 수 없다.
• s[2]은 g[3]을 만족시킬 수 없다.

 

 

 

 

 

❒ Solution

---

public int findContentChildren(int[] g, int[] s) {
    // 효율적으로 그리디 알고리즘을 해결하기 위해서 각 배열 정렬
    Arrays.sort(g);
    Arrays.sort(s);
    
    int gMarker = 0;
    int sMarker = 0;
    
    while (gMarker < g.length && sMarker < s.length) {
        if (g[gMarker] <= s[sMarker]) {
            gMarker ++;
        }
        sMarker ++;
    }
    return gMarker;
}

우선 배열 g와s를 정렬해줘야 한다. 그러면 왜 정렬해줘야 할까? 이 문제에서 배열을 정렬하는 이유는 쿠키의 크기를

아이들의 요구 만족도에 맞춰 효율적으로 할당하기 위함이다. 즉, 작은 쿠키부터 순차적으로 작은 만족도를 가진

아이에게 할당하는 방식으로, 더 많은 아이를 만족시킬 수 있는 선택을 하기 위함입니다.