[Python] LeetCode - 1996. The Number of Weak Characters in the Game

LeetCode 1996번 The Number of Weak Characters in the Game 문제는 캐릭터의 공격력과 방어력으로 weak character의 수를 구한 문제다. 난이도는 중(Medium)이며 그리디 알고리즘을 통해 해결할 수 있다.

 

리트코드 1996번 The Number of Weak Characters in the Game 문제 정보

알고리즘 분류

- Greedy

난이도

- Medium

 

문제 요약

• 각 캐릭터의 attack(공격력), defense(방어력)이 주어진다.
• 나보다 공격력과 방어력이 모두 높은 다른 캐릭터가 있다면 나는 weak character이다.
• weak character의 수를 구하라.

 

문제 풀이 과정 1

 

• 캐릭터의 수 (N)이 10^5까지이므로 O(nlogn) 알고리즘 정도로 구해야 한다.
  • 나와 다른 모든 캐릭터를 한번씩 비교해서는 안된다.
  • 정렬을 쓰긴 써야할 것 같다.
• 캐릭터를 공격력 내림차순 + 방어력 오름차순으로 정렬한 뒤, 순서대로 탐색하면서 나보다 방어력이 높은 캐릭터가 있었는지 확인한다.

코드

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
				# attack desending, defense acending
				properties.sort(key=lambda x: (-x[0], x[1])) 
        ans, max_def = 0, 0
        for property in properties:
            # this is weak character because there is any other greater defense
            if max_def > property[1]:
                ans += 1
                
            max_def = max(max_def, property[1])
        
        return ans

• 시간복잡도: 정렬 (O(nlogn)) + for문 (O(n))
• 공간복잡도: O(1)

 

문제 풀이 과정 2

 

• 캐릭터의 수 (N)이 10^5까지이므로 O(nlogn) 알고리즘 정도로 구해야 한다.
  • 나와 다른 모든 캐릭터를 한번씩 비교해서는 안된다.
  • 정렬을 쓰긴 써야할 것 같다.
• 캐릭터를 공격력 내림차순 + 방어력 오름차순으로 정렬한 뒤, 순서대로 탐색하면서 나보다 방어력이 높은 캐릭터가 있었는지 확인한다.

코드

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        attack_dict = collections.defaultdict(list)
        for att, dfs in properties:
            attack_dict[att].append(dfs)
        
        attacks = list(attack_dict.keys())
        attacks.sort(reverse=True)
        max_dfs = 0
        ans = 0
        for attack in attacks:
            dfs_list = attack_dict[attack]
            local_max = 0
            for dfs in dfs_list:
                if dfs < max_dfs:
                    ans += 1
                local_max = max(local_max, dfs)
            max_dfs = max(max_dfs, local_max)
        
        return ans

• 시간복잡도: 정렬 (O(mlogm): m은 distinct num of attack value) + 2중 for문 (O(n))
  • 어차피 최악의 경우에는 O(nlogn)임
• 공간복잡도: O(n)