Codility Lesson 04 - PermCheck( JAVA )

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

PermCheck coding task - Learn to Code - Codility

 

문제

- 배열 A는 비어있지 않은 배열이다.

- 배열 A는 순열이다.( 1 ~ N까지 중복없이 하나씩 존재 )

- 예시 : A = [4, 1, 3, 2]는 순열, A = [4, 1, 3]은 2가 빠졌기에 순열이 아니다.

- A배열이 순열인지 아닌지를 판단하는 문제

 

제한조건

• 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].

N은 1 ~ 100,000 범위의 정수이다.

A의 각 원소는 1 ~ 1,000,000,000 범위의 정수이다.

 

풀이

- A의 원소들과 N은 제한조건에 의해서 int 범위 내의 수이다.( int : -2147483648 ~ 2147483647 )

- 배열 A를 오름차순으로 정렬( Arrays.sort() 메소드를 활용, default : 오름차순 정렬 )

- int tmp = 1부터 오름차순으로 정렬된 배열의 원소들을 체크한다.( for문 활용 )

- tmp 원소가 있으면 tmp += 1하여 다음 원소를 체크

- for문을 순회하면서 tmp와 같지 않을 경우에 return 0, 모두다 돌았을 경우에 return 1

 

시간복잡도는 O(N)으로 예상

 

소스코드

// 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 tmp = 1;
        
        Arrays.sort(A);

        for( int i:A ){
            if( tmp == i ){
                tmp++;
            }else{
                return 0;
            }
        }

        return 1;
    }
}