[ 알고리즘 ] 1996. The Number of Weak Characters in the Game

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 1996. The Number of Weak Characters in the Game를 풀고 작성한 글입니다.

문제

요구사항

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

제약사항

• 2 <= properties.length <= 105
• properties[i].length == 2
• 1 <= attacki, defensei <= 105

풀이

접근법

정렬을 활용한 두 가지 풀이가 존재한다.

1. 내부 정렬 메서드 사용
2. 계수 정렬 사용

첫 번째 풀이

먼저 아래와 같이 내부 정렬 메서드인 sort() 를 사용해서 문제를 해결할 수 있다.

먼저 attack 을 기준으로 내림차순 정렬하고 만약 동등한 경우 defense 를 기준으로 오름차순을 정렬한다.

이렇게 할 경우 동일한 attack 값에 대해 defense 값이 달라지는 경우를 추가적으로 고민하지 않아도 무조건적으로 반복문을 수행하며 현재의 defense 값이 만약 이전의 가장 큰 defense 값보다 작을 경우 무조건 attack 값과 defense 값 모두 작은 경우이기 때문에 셈을 하면 되고 클 경우 이전의 가장 큰 defense 값을 그 값으로 변경하면 된다.

def solution(properties: list[list[int]]) -> int:
    properties.sort(key=lambda x: (-x[0], x[1]))
    maximum_defense: int = properties[0][1]
    
    answer: int = 0
    for _, defense in properties:
        if defense < maximum_defense:
            answer += 1 
        else:
            maximum_defense = defense
    
    return answer

두 번째 풀이

다음으로 계수 정렬(Count Sort)를 사용해서 문제를 해결할 수 있다.

주어진 입력값에서 가장 큰 attack 값을 길이로 가진, 해당 attack 값을 인덱스로 하고 값을 defense 로 하는 새로운 배열을 생성한다.

이때 중요한 점은 각 attack 값을 인덱스로 하는 요소를 가장 큰 defense 값으로 해야 한다는 점이다.

이후 배열에 대해 반복문을 가장 마지막 요소부터 역으로 수행하며 만약 현재의 배열 요소가 바로 다음의 배열 요소보다 클 경우 이를 현재의 배열 요소로 바꾼다.

마지막으로 다시 입력값인 properties 배열에 대해 반복문을 수행하며 만약 현재의 attack 값의 인덱스 요소보다 하나 큰 값의 요소인 defense 값이 현재의 defense 값보다 클 경우, 다시 말해 attack 값과 defense 값이 모두 더 작을 경우 셈을 한다.

def solution(properties: list[list[int]]) -> int:
    maximum_attack: int = 0
    for attack, _ in properties:
        if attack > maximum_attack:
            maximum_attack = attack
    
    bucket: list[int] = [ 0 for _ in range(maximum_attack+2) ]
    for attack, defense in properties:
        if bucket[attack] < defense:
            bucket[attack] = defense
    
    for idx in range(maximum_attack+1, 0, -1):
        if bucket[idx] > bucket[idx-1]:
            bucket[idx-1] = bucket[idx]
    
    answer: int = 0
    for attack, defense in properties:
        if defense < bucket[attack+1]:
            answer += 1
    
    return answer

시간 복잡도

첫 번째 풀이

첫 번째 풀이의 경우 내부 정렬 메서드를 사용하기 때문에 결과적으로 시간 복잡도는 O(NlogN)이다.

두 번째 풀이

두 번째 풀이의 경우 주어진 입력값 N에 대한 반복문 수행과 더불어 최대 attack 값보다 하나 큰 만큼의 크기를 가진 배열을 생성하고 반복문을 수행해야 하기 때문이 시간 복잡도는 O(N+K)이다.