[LeetCode] 3577. Count the Number of Computer Unlocking Permutations

https://leetcode.com/problems/count-the-number-of-computer-unlocking-permutations/description/?envType=daily-question

LeetCode - Count the Number of Computer Unlocking Permutations

문제 유형: 수학, 조합론, 애드 혹

문제 난이도: Medium

 

문제

You are given an array complexity of length n.

There are n locked computers in a room with labels from 0 to n - 1, each with its own unique password. The password of the computer i has a complexity complexity[i].

The password for the computer labeled 0 is already decrypted and serves as the root. All other computers must be unlocked using it or another previously unlocked computer, following this information:

• You can decrypt the password for the computer i using the password for computer j, where j is any integer less than i with a lower complexity. (i.e. j < i and complexity[j] < complexity[i])
• To decrypt the password for computer i, you must have already unlocked a computer j such that j < i and complexity[j] < complexity[i].

Find the number of permutations of [0, 1, 2, ..., (n - 1)] that represent a valid order in which the computers can be unlocked, starting from computer 0 as the only initially unlocked one.

Since the answer may be large, return it modulo 10^9 + 7.

Note that the password for the computer with label 0 is decrypted, and not the computer with the first position in the permutation.

 

n개의 숫자가 들어있는 complexity배열이 주어진다. 각 숫자는 i번째 컴퓨터의 비밀번호에 대한 복잡도를 말한다.

0번 컴퓨터는 이미 해독되어있다.

j번째 컴퓨터가 뒤의 i번째 컴퓨터보다 complexity값이 낮으면, 즉 (j < i, complexity[j] < complexity[i])이면 j번째 컴퓨터로 i번쨰 컴퓨터를 풀 수 있다.

모든 컴퓨터를 해독하는 순서의 경우의 수를 구하시오.

 

풀이

사실 0번째가 해독되어있으므로, 1 ~ n-1구간에서 0번째보다 작거나 같은 수가 없다면, 어느 순서로 하든 상관없다. 

대신, 해당 구간에서 있다면, 완전 불가능하므로 경우의 수는 0이 된다.

 

나머지 경우, n-1개를 배치하면 되므로, (n-1)!가 정답이다.

 

 

코드

C++

using ll = long long;

const int MOD = 1e9 + 7;

ll fact[100001];
bool built = false;
void build() {
    if (built) return;
    built = true;
    fact[0] = 1;
    for (int i = 1; i <= 100000; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
}


class Solution {
    int MOD = 1e9 + 7;
public:
    int countPermutations(vector<int>& complexity) {
        int n = complexity.size();
        if(*min_element(complexity.begin()+1, complexity.end()) <= complexity[0]) {
            return 0;
        }
        build();
        return fact[n-1];
    }
};

 

Go

const MOD int = 1_000_000_007
func countPermutations(complexity []int) int {
    n := len(complexity)
    minVal := math.MaxInt
    fact := make([]int, n);
    fact[0] = 1
    for i := 1; i < n; i++ {
        minVal = min(complexity[i], minVal)
        if minVal <= complexity[0] {
            return 0
        }
        fact[i] = fact[i-1] * i % MOD
    }
    return fact[n-1]
}

 

Rust

impl Solution {
    pub fn count_permutations(complexity: Vec<i32>) -> i32 {
        let MOD: i64 = 1_000_000_007;
        let n = complexity.len();
        let mut fact = vec![0i64; n];
        fact[0] = 1;

        let mut min_val = i32::MAX;
        for i in 1..n {
            min_val = min_val.min(complexity[i]);
            if min_val <= complexity[0] {
                return 0
            }
            fact[i] = fact[i-1] * (i as i64) % MOD;
        }

        fact[n-1] as i32
    }
}