[코딜리티] codility lesson4 Counting Elements - PermCheck 100%

문제.

Programming language:                 C                        C++                        C#                        Go                        Java                        JavaScript                        Lua                        Objective-C                        Pascal                        PHP                        Perl                        Python                        Ruby                        Scala                        Swift 2                        Swift 3                        VB.NET                    

A non-empty zero-indexed array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2

is a permutation, but array A such that:

A[0] = 4 A[1] = 1 A[2] = 3

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

int solution(int A[], int N);

that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2

the function should return 1.

Given array A such that:

A[0] = 4 A[1] = 1 A[2] = 3

the function should return 0.

Assume that:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [1..1,000,000,000].

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).

Elements of input arrays can be modified.

Copyright 2009–2017 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

풀이.

12345678910111213141516171819202122232425262728293031

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8

        int total = 0;
        int sumA = 0;

        for( int i = 1 ; i <= A.length ; i++){
            total += i;
            sumA  += A[i-1];
        }
        
        if(total != sumA) return 0;
        
        int[] chk = new int[A.length];
        //System.out.println(chk[0]);
        for( int i : A ){
            if(i > A.length) return 0;
            if(chk[i-1] != 0) return 0;
            chk[i-1] = i;
        }

        return 1 ;
    }
}

설명.

배열의 값들이 올바른 수열 을 이루고 있는지 검사하여라.

함정. 시간 복잡도를 줄이지 못하면 아무 소용이 없다.
작전은 내가 좋아하는 선형 프로그래밍 + 분기문 없음 + 네거티브 프로그래밍

1차 메인 알고리즘.
수열이 잘 이루어 졌는지 가장 빠르게 검사 하고 통과 못하면 즉시 프로그램 종료
(이 것 만으로도 꽤 높은 점수를 얻을 수 있다.)

1차 검사 통과후
카드 뽑기를 하며 불량 검사 중 판별시 프로그램 종료.