[LeetCode] 455. Assign Cookies - Python

leetcode.com/problems/assign-cookies/

Assign Cookies - LeetCode

자바로 풀었던 문제, 파이썬으로 풀어보기 !

 

JAVA >>>

자바로 풀었던 내용

import java.util.*;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int content = 0;
        Arrays.sort(g);
        Arrays.sort(s);

        int find = 0;
        for (int i = 0; i < s.length; i++) {
          for (int j = find; j < g.length; j++) {
            if(s[i] >= g[j]){
              content++;
              find = j + 1;
              break;
            }
          }
        }

        return content;
    }
}

다른 자바 풀이

    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int greed = 0;
        for (int cookie = 0; greed < g.length && cookie < s.length; cookie++) {
          if(s[cookie] >= g[greed]){
            greed++;
          }
        }

        return greed;
    }

 

파이썬 풀이

class Cookies0401:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort(reverse=True)
        s.sort(reverse=True)

        content = 0
        index = 0
        for cookie in range(0, len(s)):
            for greed in range(index, len(g)):
                if s[cookie] >= g[greed]:
                    content += 1
                    index = greed + 1
                    break

        return content

 

---

배열을 내림차순으로 정렬한다. (오름차순 정렬하면 런타임이 훨씬 길어져서 좋지 않다.)

g 배열의 길이와 상관없이, s (쿠키) 의 길이가 최대 리턴가능한 수가 된다. 쿠키가 없으면 줄 수가 없으니까. 그래서 s 배열을 기점으로 for문을 돌렸다.

 

만약 쿠키의 크기가 욕심보다 크거나 같으면, ( s[cookie] >= g[greed]: ) 만족도 변수에 1을 더한다. 그리고 해당 쿠키는 이미 아이에게 준 쿠키이므로, 해당 쿠키 이후의 요소만 검색하기 위해 따로 만들어둔 index 변수에 현재 위치 index +1 을 한다. 그렇게 하면 처음에는 0부터 검색하고, 쿠키를 준 다음부터는 해당 쿠키 이후의 요소부터 검색할 수 있다.

가능한 쿠키를 모두 배분하고 나면 content를 리턴한다.