1395-kir3i.md

1395. Count Number of Teams

Solution

• 시간복잡도: O(N^2)

• 알고리즘

  구현, 선형탐색

• 풀이설명

  N이 최대 1000이므로 모든 rating 조합을 보면 시간초과가 납니다.

  1. rating을 순회하면서 각 값을 기준으로 왼쪽 리스트, 오른쪽 리스트로 나눠서 기준값보다 큰 값의 수를 각각 구합니다. (Lbig, Rbig)
  2. 모든 rating값은 unique하므로 기준값보다 크지 않은 값은 모두 작은 값입니다.
  3. 이 때 가능한 경우의 수는 왼쪽 리스트에서 기준값보다 큰 값의 수 * 오른쪽 리스트에서 기준값보다 작은 값의 수 + 왼쪽 리스트에서 기준값보다 작은 값의 수 * 오른쪽 리스트에서 기준값보다 큰 값의 수 입니다. 각 기준값에 대해 경우의 수를 게산해서 모두 합하면 답이 됩니다.

• 소스코드

class Solution:
    def numTeams(self, rating):
        ans = 0
        for i, x in enumerate(rating):
            if i == 0 or i == len(rating):
                continue
            Llen = i
            Rlen = len(rating) - i - 1
            Lbig = len([n for n in rating[:i] if n>x])
            Rbig = len([n for n in rating[i+1:] if n>x])
            ans += Lbig*(Rlen-Rbig) + Rbig*(Llen-Lbig)
        return ans