[코딜리티] codility lesson 6 sorting - Distinct 100%

문제.

Programming language:                 C                        C++                        C#                        Go                        Java                        JavaScript                        Lua                        Objective-C                        Pascal                        PHP                        Perl                        Python                        Ruby                        Scala                        Swift 2                        Swift 3                        VB.NET                    Human language:                 Chinese                English            

Write a function

int solution(int A[], int N);

that, given a zero-indexed array A consisting of N integers, returns the number of distinct values in array A.

Assume that:

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

For example, given array A consisting of six elements such that:

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

the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

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

풀이.

12345678910111213141516171819202122232425262728293031323334353637383940414243

// 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;
        mysort(A,0,A.length-1);
        
        int distinctCount = 1, check = A[0];
        for( int i : A) if(check != i){ distinctCount++; check = i;}

        return distinctCount;
    }
    
    public static void mysort(int[] A, int left, int right){
        if( left < right){
        int pivot = A[left];
        int j = right;
        int i = left +1;
        
            for( ; i <= right ; i++){
                while(A[i] < pivot && i < right) i++;
                while(A[j] > pivot && j > left ) j--;

                if( i < j){
                    int tmp  = A[i];
                    A[i]     = A[j];
                    A[j]     = tmp;
                }
            }
            A[left]  = A[j];
            A[j]     = pivot;
            
            mysort(A, left, j-1);
            mysort(A, j+1, right);
        }
    }    
}

설명.

A배열 요소들의 Distinct Count 를 출력 하라.



레슨 제목에 힌트가 있는 것 같다. 정렬하고 숫자세기인데 위 요구사항에 맞춘 적절한 정렬알고리즘을 선택해야 할 것이다. 근데 그것도 퀵소트를 해야 한다고 하는 것 같다.

함수 정의 상태를 보아하니 리커시브는 물건너 간 것 같다.

그런데 꼭 이러고 돌리면 100% 안되드라!..
어째든. 퀵소트를 뱅글뱅글 돌려서 디스팅트 카운트를 하기로 하고 GO~!

결과적으로 100%를 달성 하긴 했다 작전이 한번에 먹혀 들어 간 것도 오랫만 인듯.
근데 퀵소트 함수가 어딘지 모르게 좀 구린 거 같은 느낌은...