[LeetCode] 1395. Count Number of Teams (파이썬/python)

🎈문제

https://leetcode.com/problems/redundant-connection/

 

🎁어떤 알고리즘?

1. 모르겠음 ㅡㅡ

2. 백트래킹과 3중 for문 두 번의 실패를 겪고 결국 찾아본 코드

 

💻코드

class Solution:
    def numTeams(self, rating: List[int]) -> int:

        ans = 0
        left = [0 for _ in range(len(rating))]
        right = [0 for _ in range(len(rating))]
        for i in range(len(rating)):
            for j in range(0,i):
                if rating[i] > rating[j]:
                    left[i] = left[i] + 1
                    ans = ans + left[j]
                else:
                    right[i] = right[i] + 1
                    ans = ans + right[j]

        return ans

 

 

❌실패 사례 -> 시간 초과

1. 백트래킹

class Solution:
    def numTeams(self, rating: List[int]) -> int:

        #### 백트래킹
        soldier = []
        cnt = 0
        n = len(rating)

        def dfs(start):
            nonlocal cnt

            if len(soldier) == 3:
                if soldier[0] < soldier[1] < soldier[2] or soldier[0] > soldier[1] > soldier[2] :
                    cnt += 1
                    return
                return

            for i in range(start,n):
                soldier.append(rating[i])
                dfs(i+1)
                soldier.pop()
            return

        dfs(0)

        return cnt

 

2. 3중 for문

class Solution:
    def numTeams(self, rating: List[int]) -> int:



        #### 완전 탐색
        n = len(rating)
        cnt = 0

        for i in range(n):
            for j in range(i+1,n):
                for k in range(j+1,n):
                    if rating[i]<rating[j]<rating[k] or rating[i]>rating[j]>rating[k]:
                        cnt += 1

        return cnt