[codility]PermCheck

Q. 1부터 시작해서 N까지 순서는 무작위 이나, 숫자가 순차적으로 1씩 값이 올라가야 하는 배열이 정상인지 판단해라.

    정상이면 1, 빠진값이 있으면 0으로 리턴

    {4, 1, 3, 2}  = 1

    {4, 1, 3}     = 0

 

[성공한 버전]

중복값 여부를 찾기 위해 HashMap을 사용 했다.(HashSet 이 공간을 덜 먹나..? 그건 잘 모르겠다)

계산도 필요없고 중복값, 최소값, 최대값만 찾으면 된다.

 

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int minVal = 1000000000;
        int maxVal = 0;
        int rtnVal = 1;
       
        Map<Integer, Integer> chkArr = new HashMap<Integer, Integer>();
        for(int i : A){
            if(chkArr.get(i) != null){
                rtnVal = 0;

                break;
            }
            chkArr.put(i, i);
            minVal = Math.min(minVal, i);
            maxVal = Math.max(maxVal, i);
        }
       
        if(minVal != 1) rtnVal = 0;
        if(maxVal != A.length) rtnVal = 0;
       
        return rtnVal;
    }
}

 

[실패한 버전]

이건 분명 수학공식이 있을꺼야 라고 생각하고 어렵게 한 버전... 

합계를 계산하는 방식으로는 함정을 빠져 나갈 수 없더라.. 결국에는 포기함.

ex. 1, 4, 1

     9, 5, 7, 3, 2, 7, 3, 1, 10, 8

 

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        long actVal = 0;
        long sumVal = 0;
        int minVal = 1000000000;
        int maxVal = 0;
       
        for(int i : A){
            minVal = Math.min(minVal, i);
            maxVal = Math.max(maxVal, i);
            sumVal = sumVal + i;           
        }
        actVal = (minVal - 1) + (A.length * (A.length + 1) / 2);
       
        int rtnVal = 1;
        if(minVal != 1){
            rtnVal = 0;           
        }else if(maxVal != (minVal - 1) + A.length){
            rtnVal = 0;
        }else if(actVal != sumVal){
            rtnVal = 0;
        }
        return rtnVal;       
    }
}