Lesson 2: PermCheck (Perm Check)

https://codility.com/programmers/lessons/2
Lesson 2 - PermCheckの答えがこちらになります。

この問題のcomplexityは下のようになっていますね。

最悪実行時間はO(N)ってことは、多分「ループはネストしてない」とかというお話で、最悪メモリ使用量がO(N)なのは「入力のサイズに比例したメモリ使っていい」というお話のはず。

========================================================================

Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage 

(not counting the storage required for input arguments).

========================================================================

で、下のコードになります。バケツ戦略？みたいなよくある手法です。

まず、配列B（入力と同じサイズ＝最悪メモリ使用量O(N))を用意して、そこにフラグを建てていきます。この配列Bでは、B[i] = 1の場合、iという数字が配列Aの中で見つかったという事になります。０なら見つからなかったという意味にします。

最初に配列Aをスキャンして配列Bにフラグをたてていきます。このときN以上の数字があったら、その時点でpermutationできてないので結果がわかっておしまい、そうでなければ配列Bのスキャン。

配列Bをスキャンしている間に０があったら、その数字は欠けているので、permutationになっていません。全部１だったら、出来てます、ってことですね。

================================================================================

int solution(int A[], int N) 

{

    int B[N];

    memset(B, 0x00, sizeof(B));

    int i;

    for (i = 0; i < N; i++){

        if (A[i] > N){

           return 0;

        }

        B[A[i] - 1] = 1;

    }

    

    for (i = 1; i < N; i++){

        if (B[i] == 0){

           return 0;

        }

    }

    

    return 1;

}