leetcode medium : The Number of Weak Characters in the Game

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

The Number of Weak Characters in the Game - LeetCode

 

딱봐도 스택냄새가 나는 문제..

나보다 쎈(attack과 defense가 모두 greater than인) 요소가 하나라도 있으면 나는 weak이다.

이 weak한 요소의 개수를 세는 것.

뭔가 정렬이랑 스택냄새가 풀풀 났는데 구체적인 구현 방법은 떠오르지 않아 정답지를 참고했다.

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        answer = 0
        stack = []
        
        properties.sort(key=lambda x:(x[0],-x[1]))
        for a,d in properties:
            while stack and stack[-1][1] < d:
                stack.pop()
                answer += 1
            stack.append((a,d))
        
        return answer

흠.. 이건 좀 심한데!? 5.6초라니;; optimization이 좀 필요해보인다. 리트코드에서 후하게 채점해줘서 Success인거같고 보통의 코딩 사이트에서는 웬만하면 얄짤없이 Time Limit Exceeded를 띄웠을거같은..

이경우 시간복잡도는 O(N log N)이고 공간복잡도는 최대 O(N)이다.

 

다른 풀이 방법을 보자.

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        
        properties.sort(key=lambda x: (-x[0],x[1]))
        
        ans = 0
        curr_max = 0
        
        for _, d in properties:
            if d < curr_max:
                ans += 1
            else:
                curr_max = d
        return ans

attack을 내림차순으로, defense를 오름차순으로 정렬하고 있다.

대충 알거같다.

1. 일단 attack이 제일 큰 놈들의 경우 자기보다 쎈 애들이 없으니까 아무도 weak하지 않다.

위의 코드에서는 attack이 내림차순 정렬이라 처음 for문 시작할때 attack 큰놈들부터 보게 되는데

같은 attack이라면 defense는 오름차순 정렬이라서 if d < curr_max 조건에 아무도 안걸린다.

그래서 attack이 젤 큰놈들은 answer에 하나도 카운트하지 않는다.

 

2. attack이 젤 큰놈들 중에 defense가 젤 큰놈의 값이 10이라고 치자(예를 들어). 그럼 어쨌든 attack이 걔보다 작은놈들은 defense가 10보다 작을때 무조~~건 weak이다. 그니까 max값을 갱신해서 저장을 해놓는거고 만약 max값이 더 큰게 나타나면 주저없이 갱신하면 된다. 왜냐하면 defense는 오름차순 정렬이라서 attack이 같을때에는 if d < curr_max조건에 걸일 일이 없음. 현재 보고 있는 애의 defense값보다 더 큰 애가 있고 걔가 attack값도 더 커야만 저 조건에 걸린다는 것.

 

이 해답 만든 사람 천재인거같다 ㅎㄸ