Codility Lesson 06 - Distinct( JAVA )

https://app.codility.com/programmers/lessons/6-sorting/distinct/

Distinct coding task - Learn to Code - Codility

 

문제

- N개로 이루어진 A배열이 주어진다.

- 각각 중복되지 않는 수들을 구하라.

- 예시 : A[0] = 2 A[1] = 1 A[2] = 1 A[3] = 2 A[4] = 3 A[5] = 1

- return 3( 1, 2, 3이 중복되지 않는 수 )

 

제한조건

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000].

N은 0 ~ 100,000 사이의 정수이다.

A의 각각 원소들은 -1,000,000 ~ 1,000,000 사이의 정수이다.

 

풀이

- A 배열을 정렬( Arrays.sort(), deafult : 오름차순 )하여, for문으로 순회하며 수가 다른 경우가 있을 경우 count한다.

- 배열이 비어있을 경우와 원소가 1개만 있을 경우 예외처리 해준다.

- A[0] 첫원소를 tmp에 초기화 및 count 변수는 1로 초기화( 첫 원소는 카운팅 한 것으로 ), for문은 int i=1 부터 순회하게 해준다.

 

예상 시간복잡도 : O(N) - for문 모두 순회하는 경우

 

소스코드

// 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
        if( A.length == 0 ){
            return 0;
        }else if( A.length == 1){
            return 1;
        }

        Arrays.sort(A);
        int count = 1;
        int tmp = A[0];
        for( int i=1; i<A.length; i++ ){
            if( tmp != A[i] ){
                count++;
                tmp = A[i];
            };
        }

        return count;
    }
}