[python] itertools.permutations

[문제링크]
https://leetcode.com/problems/maximum-compatibility-score-sum/

완전탐색 문제인데, itertools의 순열을 이용해서 큰 고민 안하고 푸니,
3696ms 라는 런타임이 나와버림.

런타임은 길지만, 순열 자체 조합으로의 메모리 사용량은 심하게 증가하지는 않는다.

[단순무식 코드: Run time, 3696ms]

from itertools import permutations

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        stu_per = permutations(students)
        men_per = permutations(mentors)
        
        m = len(students)
        n = len(students[0])
        answer = 0
        for stu in stu_per :
            for men in men_per :
                temp = 0
                for i in range(m):
                    for q in range(n):
                        if stu[i][q] == men[i][q]:
                            temp += 1
                        
                if temp > answer:
                    answer = temp

        return answer

[submission Detail link]
https://leetcode.com/submissions/detail/529369418/

[60ms Runtime 코드(다른사람코드)] // 이해하고 공부하기

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        
        @cache
        def cost(i, j):
            return sum(s == m for s, m in zip(students[i], mentors[j]))
        
        def neighbors(mask):
            for i in range(len(mentors)):
                if mask & (1 << i) == 0:
                    yield i, mask | (1 << i)
        
        @cache
        def dp(i, mask):
            if i == len(students):
                return 0
            
            ans = 0
            for nei, nmask in neighbors(mask):
                ans = max(ans, cost(i, nei) + dp(i + 1, nmask))
            
            return ans
        
        return dp(0, 0)

동일한 문제 C++과 JAVA 버전으로도 풀어보기.