[Codility(코딜리티)] Lesson4. PermCheck (100%)

Lesson 4 Counting Elements - PermCheck (Java Solution)

app.codility.com/programmers/lessons/4-counting_elements/perm_check/

PermCheck coding task - Learn to Code - Codility

---

문제

N개의 길이를 가진 배열 A가 주어진다

A는 1~N까지 각 요소를 한개씩 모두 가지고 있어야 한다

예를 들면, A = {4,1,3,2}, A의 길이는 4이다

즉, 1,2,3,4의 원소를 가지고 있으니 True이다

B = {4,1,3} 이면, 1,2,3의 원소 중 2가 빠져있다 따라서 False이다

rue이면 1, 아니면 0을 출력한다

 

해결

이 문제는 Set으로 간단히 해결할 수 있었다

set.contain()의 시간복잡도는 O(1)이기 때문에,

배열의 요소를 set에 넣고, 

result defalut 값으로 1을 설정하고,

contain()으로 1씩 찾으면서 없는 경우에 result를 0으로 만들고 break 한다

그리고 마지막에 result를 출력해주면 된다

시간복잡도는 배열을 set에 넣는 시간 O(N)에다가 

배열의 길이 만큼 돌면서 숫자를 찾는 최악의 시간복잡도는 O(N)이고 최적은 O(1) 이다

public class PermCheck {

    public int solution(int[] A) {
        int result = 1;
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i : A) hashSet.add(i);
        for (int i=1; i<=A.length; i++) {
            if (!hashSet.contains(i)) {
                result = 0;
                break; // 시간복잡도를 줄이기위함
            }
        }
        return result;
    }
 }