[python3] 1996. The Number of Weak Characters in the Game

풀이 일자: 22.09.09

난이도: [Medium]

분류: [Greedy, Sorting]

문제 내용

주어진 character 집합에서 상대적으로 ATK, DEF가 다른 character보다 낮은 경우 Weak라고 하며 Weak character의 수를 찾는 문제.

 

문제 해결 흐름

1. 다른 ATK, DEF보다 낮은 player의 수를 찾아야 하니까 뭔가 극단적인 값을 이용하면 되지 않을까?

→ Greedy하게 현재 주어진 배열에서 ATK와 DEF가 상대적으로 가장 높은 값을 가지고 시작하자.

2. 가장 높은 값을 가지고 시작하되 좀 더 쉽게 만드는 방법이 있을까?

→ 배열이 ATK 내림차순, DEF 오름차순으로 정렬하면 비교하는데 크게 문제가 없겠다.

 

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        ans = 0
        properties.sort(key= lambda x : (-x[0],x[1]))
        maxATK, maxDEF = 0 , 0
        
        for ATK, DEF in properties:
            if (ATK < maxATK) and (DEF < maxDEF):
                ans += 1
            elif DEF > maxDEF:
                maxATK = ATK
                maxDEF = DEF
            else:
                pass
        return ans

→  현재 여기에서 sort하는 과정이 시간이 많이 걸리는 것으로 판단하여 sort기준을 줄이고 추가적인 변수를 설정하여 기준을 줄인 것에 대한 보조적인 코드를 추가하였다. 시간은 조금 줄었으나 크게 줄지 않았다.

 

다른 해결 방식

→ 큰 차이는 없었으나 Runtime 속도가 빠른 코드의 경우 for문에서 in으로 뽑아오는 코드가 아니라 length를 이용해 for을 돌리고 index로 접근하였다.

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda x:(-x[0],x[1])) #check the x[0] if they are same then check the x[1]
        
        mxattack=properties[0][0]
        mxdefense=properties[0][1]
        
        count=0
        for i in range(1,len(properties)):
            if properties[i][0]<mxattack and properties[i][1]<mxdefense:
                count+=1
            else:
                mxattack=properties[i][0]
                mxdefense=properties[i][1]
        return count

https://leetcode.com/problems/the-number-of-weak-characters-in-the-game/discuss/2552511/Python-3-Solution-Faster-then-94-10-line-sol.

문제 링크

https://leetcode.com/problems/the-number-of-weak-characters-in-the-game/