Contents

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

   Aug 21, 2020     4 min read     - Comments

1. 문제

원의 중심이 (K, 0) 이고, 반지름이 A[k]인 원 N개가 주어졌을 때, 겹치는 원의 개수를 반환하는 문제이다.

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

이런 모양의 그림이 나오게 된다.
1

이미지 해설 접기/펼치기

  • K = 0 일 때 (기준 빨간색, 겹치는 원 파란색)
    2
    겹치는 원의 숫자가 3개이다. k = 0은 제외 시킨다.

  • k = 1 일 때
    3
    겹치는 원의 숫자가 4개이다. 3 + 4 = 7

  • k = 2 일 때
    4
    겹치는 원의 숫자가 2개이다. 7 + 2 = 9

  • k = 3 일 때
    5
    겹치는 원의 숫자가 1개이다. 9 + 1 = 10

  • k = 4 일 때
    6
    겹치는 원의 숫자가 1개이다. 10 + 1 = 11

  • k = 5 일 때
    7
    겹치는 원의 숫자가 0개이다. 답은 11이 된다.

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) {
    int* discS = (int*)malloc(sizeof(int) * N);
    int* discE = (int*)malloc(sizeof(int) * N);
    
    for(int i = 0; i < N; i++){
        discS[i] = i > A[i] ? i-A[i] : 0;
        discE[i] = N-i-1 > A[i] ? i+A[i] : N-1;
    }
    quickSort(discS , 0, N-1);
    quickSort(discE , 0, N-1);
    
    int s = 0, e = 0, c = 0, result = 0;
    while(e < N){
        if(s < N && discS[s] <= discE[e]){
            c++;
            s++;
        }else{
            result += --c;
            e++;
        }
    }    
    return result < 10000001 ? result : -1;
}

  • 36 ~ 37Line 원의 크기가 0 ~ N-1 범위를 벗어나는 걸 방지하기 위한 부분
    원소의 숫자가 int의 범위를 넘어서 버리면 오류가 생기기 때문이다.

  • 43Line

    • s[0] <= e[0] c = 1
      1

    • s[1] <= e[0] c = 2
      2

    • s[2,3] <= e[0] c = 4
      3

    • s[4] > e[0] (c = 3, reslut += c = 3)
      s[4] <= e[1] c = 4
      4

    • s[5] > e[1] (c = 3, reslut += c = 6)
      s[5] > e[2] (c = 2, reslut += c = 8)
      s[5] <= e[3] c = 3
      5

    • e[4] (c = 2, reslut += c = 10) (s[6]은 없으므로 비교X)
      6

    • e[5] (c = 1, reslut += c = 11)
      7