[codility] PermCheck

(문제) non-empty Array A가 주어질 때 해당 배열이 permutation이면 1, 아니면 0 반환하는 함수 작성

 

 

(my solution)

- 처음엔 보기 좋게 낚였다. 전체 합으로 접근하면 안된다. 왜냐하면 [0, 3]인 케이스는 전체 합을 만족시켜도 permutation이 아니니까

- HashSet을 이용하니 쉽게 해결되는 문제

- 시간복잡도는 O(N)

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

// 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) {
        HashSet<Integer> permutationElem = new HashSet<>();

        for (int i = 1; i < A.length + 1; i++) {
            permutationElem.add(i);
        }

        for (int num : A) {
            if (permutationElem.contains(num)) {
                permutationElem.remove(num);
            }
        }

        return (permutationElem.size() == 0) ? 1 : 0;
    }
}

 

(chatGPT)

- 흠? 처음으로 chatGPT보다 내 코드가 더 맘에 든다.

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        boolean[] check = new boolean[N + 1];

        // 배열 A의 값들을 체크 배열에 표시
        // 배열 A가 permutation인지 확인
        for (int i = 0; i < N; i++) {
            int num = A[i];
            if (num <= N) {
                if (check[num]) {
                    return 0; // 중복된 숫자가 있는 경우 permutation이 아님
                } else {
                    check[num] = true;
                }
            } else {
                return 0; // 숫자가 N보다 큰 경우 permutation이 아님
            }
        }

        // 배열 A가 permutation인 경우 1을 반환, 아닌 경우 0을 반환
        for (int i = 1; i <= N; i++) {
            if (!check[i]) {
                return 0;
            }
        }

        return 1;
    }
}