리트코드 - 1431. Kids With the Greatest Number of Candies

https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/

Kids With the Greatest Number of Candies - LeetCode

쉬운 문제다.

문제의 목표는 각 아이가 받은 사탕의 수에 추가 사탕을 더했을 때, 그들이 최대 사탕을 가진 아이와 같거나 더 많은 사탕을 가질 수 있는지 확인하는 것이다.

1. 최대 사탕 수 파악: 먼저, 모든 아이들 중 가장 많은 사탕을 가진 아이를 찾기 위해 max(candies)를 사용한다. 모든 아이들의 사탕 수를 한 번씩 확인하여 최대값을 찾기 위함이다.
2. 각 아이별 가능성 검사: 그 다음, 각 아이가 가진 사탕의 수에 extraCandies를 더한 값이 최대 사탕 수보다 크거나 같은지를 확인한다. 이를 위해 for 루프를 사용하여 모든 아이들의 사탕 수를 확인한다.
3. 결과 저장: 각 아이별로 검사한 결과를 res 리스트에 True 또는 False로 저장한다. 아이가 추가 사탕을 받은 후 최대 사탕 수 이상을 가질 수 있다면 True, 그렇지 않다면 False를 추가한다.
4. 결과 반환: 최종 결과 리스트 res를 반환한다.

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        res = []
        maxV = max(candies) # O(n)
        for candy in candies: # O(n)
            if candy + extraCandies >= maxV:
                res.append(True)
            else:
                res.append(False)
        return res

 

• max(candies)는 O(n) 시간 복잡도를 가진다. 여기서 n은 candies 리스트의 길이다.
• for 루프는 각 아이의 사탕 수를 한 번씩 확인하므로 O(n) 시간 복잡도를 가진다.
• 따라서 전체 시간 복잡도는 O(n)

res 리스트는 각 아이에 대한 결과를 저장하기 위해 사용되므로, 공간 복잡도는 O(n)

 

다른 풀이

동일한 로직을 사용하지만, 리스트 컴프리헨션을 사용하여 가독성을 높이고 코드를 더 간결하게 만들었다.

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        maxV = max(candies) # O(n)
        return [candy + extraCandies >= maxV for candy in candies] # O(n)

시간 복잡도와 공간 복잡도는 원래의 풀이와 동일하게 O(n)이다.