455. Assign Cookies (해석 + 풀이)

조건:

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

의역: 여러분은 훌륭한 부모님이고 아이들에게 쿠키를 주고 싶어 합니다. 

각각의 아이들이 만족하는데 필요한 쿠키 수의 배열 g[i]와 쿠키(상자)의 배열 j[i]가 주어질 때 

최대한 많은 수의 아이들을 만족시키려고 할 때 만족하는 최대 아이들의 수를 반환하시오

 

(주의 사항): 쿠키 배열의 값의 합계를 기준으로 쿠키를 주는 것이 아니라 

각각을 개봉해서 안되는 포장된 쿠키 상자 배열 이라고 보고 ex g[i] = {1,2,3} 일때 쿠키 배열 j[i] = {3} 이라고 해서 1+2=3 이렇게 2명을 최대로 만족시킬 수 있는 것이 아니라 쿠키 배열의 {3} 길이가 1임으로 최대로 만족시킬 수 있는 아이의 수는 1명 뿐임 

 

의역: 3명의 아이들이 각각 본인이 만족하는 쿠키 수는 1, 2, 3 일때 현재 내가 가지고 있는 쿠키 수는 1, 1  임으로

내가 최대로 만족시킬 수 있는 아이의 수는 쿠키를 1개 바라는 아이밖에 없으므로 1을 반환

의역: 2명의 아이들이 각각 본인이 만족하는 쿠키 수는 1, 2 일때 현재 내가 가지고 있는 쿠키 수는 1, 2, 3 임으로

2명의 아이들을 모두 만족시킬 수 있으므로 2를 반환

 

풀이: 

1. 정렬 이용

class Solution {
	// 시간복잡도 O(nlog n)-Arrays.sort() 공간 복잡도 O(1)
    public int findContentChildren1(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i=0,j=0;
        int ans =0;
        while(i<g.length&&j<s.length){
            if(g[i]<=s[j]){
                ans++; i++; j++;
            }
            else{
                j++;
            }
        }

        return ans;
    }
}

2. TreeMap<Integer, Integer>의 ceilingkey() 함수 사용

class Solution {
	public int findContentChildren(int[] g, int[] s) {
        int ans=0;
        // ceilingkey(Integer key) 일 때 key의 값 보다 크거나 같은 값중에서 제일 작은 key값을 리턴
        // key는 쿠키(박스) valse는 같은 개수를 가진 쿠키(박스)의 수
        TreeMap<Integer,Integer> tmap = new TreeMap<Integer,Integer>();
        /* containsKey() 의 시간 복잡도는 log n 임으로 안쓰는 것이 더 바람직
        for (int cookie:s) {
            if(tmap.containsKey(cookie))
                tmap.put(cookie,tmap.get(cookie)+1);
            else
                tmap.put(cookie,1);
        }
        개선한 tmap 초기화 방법*/
        for (int cookie:s) {
            Integer n = tmap.get(cookie);
            n = n==null?0:n;
            tmap.put(cookie,n+1);
        }

        for (int childG:g) {
            // ceilingKey를 이용하여 각 아이들에게 줄 수 있는 쿠키(박스)의 경우를 가져오고
            Integer target = tmap.ceilingKey(childG);
            // 만약 해당 쿠키(박스)가 존재한다면
            if(target!=null){
                Integer n = tmap.get(target);
                ans++; // 아이들의 수 +1
                // valse 값이 0이 되어야 한다면 해당 쿠키(박스) 제거
                if (n <= 1)
                    tmap.remove(target);
                // valse(같은 쿠키의 수)를 -1
                else
                    tmap.put(target, n - 1);
            }
        }
        return ans;
    }
}

링크: https://leetcode.com/problems/assign-cookies/description/