[Codility] Lesson 4 : PermCheck - JAVA

문제

A non-empty 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:
 
        class Solution { public int solution(int[] A); }
 
that, given an 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.
 
Write an efficient algorithm for the following assumptions:
 
        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].

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

 

문제 해설

solution(int[] A)에 입력되는 배열 A는 비어있지 않으며 1부터 N까지 연속된 숫자를 갖는다.
숫자 N은 1 ~ 100,000까지 가능하며, 배열 A에는 1 ~ 1,000,000,000 사이의 숫자를 가질 수 있다.

먼저 순열은 1부터 N까지의 각 원소를 한 번만 포함하는 수열을 의미한다.

예를 들어 배열 A에 다음과 같이 저장되어 있을 경우
        A[0] = 4
        A[1] = 1
        A[2] = 3
        A[3] = 2
배열 A는 연속된 값을 갖는 순열이라고 할 수 있다.

그러나 배열 A가 다음과 같이
        A[0] = 4
        A[1] = 1
        A[2] = 3
값을 가질 경우 숫자 2가 빠져있기 때문에 순열이라고 할 수 없다.

이를 통해 solution(int[] A)에 입력되는 배열 A가 순일인지 확인하여
순열일 경우 숫자 1을, 아닐 경우 숫자 0을 반환해준다.

 

풀이 - 1

class Solution {
    public int solution(int[] A) {
        int max = 0;
        for(int subA : A) {
            max = Math.max(max, subA);
        }
        if(A.length == max) return 1;
        return 0;
    }
}

 

'풀이 - 1'에 대한 회고

 

문제를 보자마자 "배열 A의 최대 값이랑 배열 A의 크기가 같으면 순열아냐?"라는 생각을 했다.

그렇게 작성한 소스코드가 바로 '풀이 - 1'!

문제에서 나온 예제만 봤을 때 당연히 통과할 줄 알았다.

그런데 결과는 83%!

 

 

정확도와 퍼포먼스 모두 83%가 나왔다.

더군다나 생각대로라면 시간복잡도가 O(n)이 나올 것이라고 생각했다.

다행히 시간복잡도는 O(n) or O(n*log(n))이 나왔다.

 

 

그럼 문제는 문제 해결을 위한 알고리즘!

분명 문제를 보고 제대로 고려하지 않은 부분이 있을 것이다.

무엇일까 고민해보고 다시 시도해봐야겠다!

 

풀이 - 2

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        for(int i=0; i<A.length; i++) {
            if(A[i] != (i+1)) return 0;
        }
        return 1;
    }
}

 

'풀이 -2'에 대한 회고

 

두 번째 풀이 방법은 배열을 먼저 정렬하는 것.

그럼 숫자 1부터 순서대로 배열이 정렬될 것이다.

그리고 반복문을 돌며 index 0에는 1, index 1에는 2, index 2에는 3...이 잘 들어가있는지 확인만 하면된다.

그저 순서대로 있는지 확인만 하면 된다.

 

 

당연히 정확도와 퍼포먼스 또한 100%.

시간복잡도는 '풀이 - 1'과 동일하게 나왔다.

 

그럼 '풀이 - 1'에서 고려하지 않은 것은 무엇일까?

일단 배열 A에 중복된 숫자가 있을 수 있다는 점을 고려하지 않았다.

이게 오류의 핵심인 듯 하다.

 

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

 

만약 배열 A가 이렇게 들어왔다면 '풀이 - 1'에서는 Max 값이 4이고 배열 A의 길이도 4니까 순열이라고 판단할 것이다.

하지만 '풀이 - 2'는

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

 

이렇게 정렬한 후 값이 값이 순차적으로 증가하고 있는지 확인하면 되기 때문에 중복되는 값도 검증할 수 있다.

순열 문제는 이렇게 푸는거구나.

 

다른 사람의 풀이

import java.util.HashSet;
class Solution {
    public int solution(int[] A) {
        HashSet<Integer> set = new HashSet<Integer>();

        for(int i=0; i<A.length; i++) {
            if(A[i] > A.length) {
                return 0;
            }

            if(set.contains(A[i])) {
                return 0;
            }
            set.add(A[i]);
        }
        return 1;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

결과는 동일하니까 점수나 퍼포먼스 등의 이미지는 따로 첨부하지 않겠다!

일단 많은 사람들이 '풀이 - 2'와 동일한 방식으로 구현하였다.

그런데 위와 같이 구현한 사람도 있어서 소스코드를 가져와봤다.

 

나도 HashSet에는 값이 중복되지 않기 때문에 HashSet을 이용해 풀어보려고 했다.

하지만 굳이 HashSet을 써야할까 해서 '풀이 - 2'처럼 구현하였다.

그런데 나와 비슷하게 HashSet을 이용할 생각을 하시다니!

왠지 모르게 동질감을 느껴 코드를 가져와봤다.

 

일단 소스코드를 설명하자면 다음과 같다.

1. 배열에 저장된 값이 배열의 크기보다 크면 순열이 아니라고 판단.
2. 배열 안에 중복된 값이 있는 경우 순열이 아니라고 판단.
3. 그 외에는 순열이라고 판단.

 

물론 괜찮은 알고리즘이지만 '풀이 - 2'보다 코드 길이도 길고 비교도 많이 하기 때문에 가독성이 좋지 않다.

하지만 이런 방법도 있다는거~!