[Codility] Lesson 6 : Distinct - JAVA

문제

Write a function
 
        class Solution { public int solution(int[] A); }
 
that, given an array A consisting of N integers, returns the number of distinct values in array A.
 
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.
 
Write an efficient algorithm for the following assumptions:
 
        - 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].
 
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A)에 입력되는 A의 길이(N)는 0 ~ 100,000까지이고,
A 안에 저장되는 정수들의 범위는 -1,000,000 ~ 1,000,000이다.

A = {2, 1, 1, 2, 3, 1}일 때
A에 중복되는 값을 제외하면 1, 2, 3의 숫자 3개가 남는다.
즉, 배열 A에 중복을 제외하고 정수 값이 몇개가 있는지 반환하면 되는 문제이다.

 

풀이 - 1

import java.util.HashSet;
class Solution {
    public int solution(int[] A) {
        HashSet<Integer> setA = new HashSet<Integer>();
        for(int subA : A) {
            setA.add(subA);
        }
        return setA.size();
    }
}

 

'풀이 - 1'을 통한 회고

 

첫 풀이는 가장 쉬운 방법으로 했다.

HashSet은 중복된 값을 저장하지 않기 때문에 무조건 HashSet에 값을 다 담았다.

그리고 HashSet의 사이즈를 반환하면 당연히 중복 제거된 값이 몇 개가 있는지 알 수 있다.

 

 

정확도, 퍼포먼스가 잘 나왔고,

 

 

시간복잡도는 O(n)만 생각했는데 O(n*log(n))도 나올 수 있다고 한다.

 

풀이 - 2

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        return (int)Arrays.stream(A).distinct().count();
    }
}

 

'풀이 - 2'에 대한 회고

 

원래 '풀이 - 1'에서 끝내려고 했지만 stream을 사용했을 때 퍼포먼스가 얼마나 떨어지나 궁굼해서 해봤다.

나는 stream을 사용하는 걸 그닥 좋아하지 않는다.

특히 반복문에서!

stream을 사용하면 가독성은 굉장히 좋아진다.

하지만 Stream 객체로 만들어줘야 하기 때문에 실행 시간이 조금 더 걸린다.

 

 

그렇기 때문에 퍼포먼스가 당연히 안나오겠지.

하드웨어가 뒷받침을 잘 해주니 Stream을 통해 가독성을 높이는 것도 좋지만

조금이라도 더 시간을 단축시키기 위해서 그냥 구현하는게 더 효과적일 수도 있다.

아! 시간 복잡도는 '풀이 - 1'과 동일하게 나와서 따로 첨부하지 않았다.

 

다른 사람의 풀이 - 1

//Arrays.sort 사용
import java.util.Arrays;
public int solution(int[] A) {
    int N = A.length;
    if(0 == N) return 0;

    Arrays.sort(A);
    int count = 1;
    for (int i=1; i<N; i++){
        if(0 != (A[i -1] ^ A[i])) count++;
    }
    return count;
}

 

'다른 사람의 풀이 - 1'을 통한 회고

 

먼저 정확도, 퍼포먼스, 시간복잡도는 '풀이 - 1'과 동일하므로 따로 첨부하지 않았다.

이 소스코드는 먼저 배열을 오름차순으로 정렬하고 인덱스 1번부터 반복한다.

그리고 이전 인덱스에 있는 값과 XOR 연산을 해서 값이 같이 않으면 count을 1 증가시켜준다.

XOR 연산을 통한 방법도 있어서 가져왔다.

 

다른 사람의 풀이 - 2

public int solution(int[] A) {
    int N = A.length;
    if(0 == N) return 0;

    quickSort(A, 0, N-1);
    int distinctNum = 1;
    for (int i=1; i<N; i++){
        if(0 != (A[i -1] ^ A[i])) distinctNum++;
    }
    return distinctNum;
}

public void quickSort(int[] arr, int begin, int end) {
    int middle = (begin + end) / 2;
    int pivot = arr[middle];
    int left = begin;
    int right = end;
    int temp;

    while (left < right) { //left와 right가 만나면 루프 종료
        while (arr[left] < pivot) left++;       //left : pivot 값 보다 큰 값을 찾기 위해 이동
        while (arr[right] > pivot) right--;     //right : pivot 값 보다 작은 값을 찾기 위해 이동

        if (left <= right) { //left가 right보다 같거나 작으면 서로 값 교환해줌
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
    //부분 분할 실행
    if (begin < right) quickSort(arr, begin, right);
    if (end > left) quickSort(arr, left, end);
}

 

'다른  사람의 풀이 - 2'를 통한 회고

 

정확도, 퍼포먼스, 시간복잡도는 동일하므로 생략!

직접 퀵정렬을 구현한 소스코드라 꼭 확인해보고 싶었다.

물론 HashSet을 이용해서 쉽게 구현할 수도 있지만

알고리즘, 자료구조를 조금 더 공부해서 이렇게 정렬을 직접 구현해서 사용하는 것도 좋을 것 같다.

자료구조 학습에 도움이 될 듯하여 소스코드를 가져와봤다.