Contents

[Codility] Lesson6. Sorting-Distinct C언어 풀이

   Aug 19, 2020     2 min read     - Comments

Lessons6. Sorting(정렬)

정렬은 데이터를 일정한 순서로 배열하는 과정이다. 대체로 원소의 값에 따라 정렬하게 되는데, 원소에는 숫자, 단어 등이 포함된다.
예를 들어, 학생들을 정렬하기 위한 원소로는 그들의 키, 이름, 생년월일을 가질 수 있으며, 시민들의 수에 따라 도시를 정렬 할 수 있다. 가장 많이 사용되는 순서는 숫자와 문자 순이다.
정렬 알고리즘은 여러 가지가 있으며, 시간 복잡성과 메모리 사용 측면에서 상당한 차이가 존재한다.

1. 문제

길이가 N인 배열 A가 주어졌을 때, 중복되지 않는 원소의 개수를 구하는 문제

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

1, 2, 3이 존재하므로 3을 반환해준다.

2. 정답

첫번째 - 100점

$O(N*log(N))$ or $O(N)$

void swap(int* data, int index1, int index2)
{
    int temp = data[index1];
    data[index1] = data[index2];
    data[index2] = temp;
}

void quickSort(int* data, int left, int right) 
{
    int pivotValue = data[(left + right) / 2];
    int i = left;
    int j = right;

    while (i <= j)
    {
        while (data[i] < pivotValue) i++;
        while (data[j] > pivotValue) j--;
        if (i <= j)
        {
            swap(data, i, j);
            i++;
            j--;
        }
    }
    if (left < j)
        quickSort(data, left, j);    
    if (right > i)
        quickSort(data, i, right);    
}

int solution(int A[], int N) {
    if(N == 0) return 0;
    
    int count = 1;
    
    quickSort(A, 0, N-1);
    
    for(int i = 1; i < N; i++){
        if(A[i] == A[i-1])
            continue;
        count++;
    }
    
    return count;
}

퀵 정렬(Quick Sort)을 사용해서 A를 정렬한 뒤 중복되지 않는 원소의 합을 반환해 주었다.