1395. Count Number of Teams

1395. Count Number of Teams

https://leetcode.com/problems/count-number-of-teams/

문제

풀이(처음 풀었던 방식)

가장 쉬운 방법은 모든 경우의 수를 계산하는 것이다. 단순한 방법으로 하게 되면 시간복잡도가 O(N^3)가 나오게 된다.
최적화한 방법으로는 point를 기준으로 left와 right를 나누고 left에서 찾고, right에서 찾는 방법이다. 이렇게 하면 시간복잡도가 O(N^2)으로 단축된다.

풀이(DP 방식)

이 문제를 DP방법으로 풀고 싶었으나 감이 잡히지 않아 알고리즘 설명하는 유튜브를 보고 푼 코드이다. Example 1기준으로 설명하자면
1. rating => (2,5,3,4,1) 일 때 left => (0,1,1,2,0)이 된다.
2. right => (0,0,1,1,4) 된다.
3. left, right에서 dp방법이 적용된다.

결과

DP

Brute Force

배운점

1. 이 문제에서 DP를 어떻게 적용해야 할 지 알게 되었다.
   https://www.youtube.com/watch?v=YfMfNKVOGH0