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

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

---

정렬 후, 그리디로 풀었다.
앞에서부터 탐색하면서 탐색중인 요소가 정답이 될 수 있는지 판단해야 한다.
공격, 방어 둘 다가 작아야 하므로. 먼저 공격을 내림차순으로 정렬한다.
공격은 내림차순 정렬했기 때문에 이때동안 탐색했던 모든 요소들의 공격은 현재 탐색하는 요소의 공격보다 크거나 같다(1).
따라서, 현재 탐색중인 방어보다 큰 값이 이때까지 탐색했던 방어들 값 중 있는지만 판단하면 된다.
큰 값을 구해야 하므로 탐색 중에 방어 값들 중 최대 값을 변수(maxDepen)에 저장해두고 이를 비교하면 O(1)만에 비교가능하다.

문제에서 공격, 방어를 비교할 때 strictly greater 해야 한다고 명시되어 있다.
앞에서 공격 값은 현재 탐색하는 요소의 공격보다 크거나 같다(1) 라고 하였다.
방어값의 최대값(maxDepen)의 공격값과 탐색 중인 공격이 같은 경우는 정답이 될 수 없다.
따라서 maxDepen인 경우, 공격값이 현재 탐색 중인 공격과 같은 경우를 안나오게 해야한다.
이를위해 처음에 정렬할 때 공격값을 기준으로 내림차순 정렬했는데, 공격값이 같은 경우엔 방어값을 오름차순 정렬해준다.

ex) [[1,1],[2,1],[1,2]] -> [[2,1],[1,1],[1,2]]

시간복잡도는 O(NlogN)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1996.%20The%20Number%20of%20Weak%20Characters%20in%20the%20Game.cpp