1. 문제 소개

3577. Count the Number of Computer Unlocking Permutations

2. 나의 풀이

처음에는 모든 경우를 다 카운팅해야하는 것으로 착각했다.
그러나 배열에서 0번째 복잡도보다 작은 복잡도가 나오는 순간 문제의 조건이 어긋나고, 나타나지 않는다면 항상 $(n-1)!$개의 답이 나온다는 것을 깨닫고 쉽게 풀 수 있었다.
시간복잡도는 $O(n)$이다.

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        MOD = 10**9 + 7                # 모듈러 값 정의
        n = len(complexity)            # 전체 컴퓨터 개수
        
        # 컴퓨터 0의 복잡도가 모든 다른 컴퓨터보다 엄격히 작아야 조건을 만족한다.
        # 만약 complexity[0] >= complexity[i] 인 i>0 이 존재하면 잠금 불가 → 0 반환
        for c in complexity[1:]:
            if complexity[0] >= c:
                return 0
        
        # 조건을 만족하면 컴퓨터 1..n-1 의 순열은 모두 가능 → (n-1)! % MOD
        return factorial(n-1) % MOD    # 팩토리얼 계산 후 모듈러 적용

3. 다른 풀이

팩토리얼을 직접 구현하는 것이 더 빠르다.

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        n = len(complexity)
        for i in range(1, n):
            if complexity[i] <= complexity[0]:
                return 0

        ans, mod = 1, 10**9 + 7
        for i in range(2, n):
            ans = ans * i % mod
        return ans

4. 마무리

직접 풀어서 만족한다.