[C언어 풀이] Codility - Lessons 4, (Counting Elements) MaxCounters

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

문제

 

설명

 

N = 리턴할 배열의 크기

A[] = 문제의 배열 요소

M = A[] 배열의 크기

 

A[] 의 배열 요소의 값에 따라 N크기의 배열의 값 증가.

단, A[]의 배열 요소 중 N값 보다 큰 값이 있을 경우 A[]의 배열 요소중 가장 큰 값으로 초기화.

 

예시

N = 5, M = 7, A[]의 요소는 아래와 같을 때.

    A[M]                        Arr[N]

A[0] = 3                   

A[1] = 4                   

A[2] = 4                   

A[3] = 6                      <<-- N(5) 보다 큰 값이 있을 땐 Arr[] 배열 요소 중 가장 큰 값으로 초기화

A[4] = 1                   

A[5] = 4                   

A[6] = 4                   

 

리턴 값은 가 저장된 배열 주소 값.

 

시간 복잡도는 O(N + M)을 넘지 않아야 합니다. 즉 2중 for문은 사용 X!!!

 

해당 배열 요소의 증가 값중 가장 많이 증가한 값을 저장해야 하고,

배열 요소중 N보다 큰 값이 있을 경우 가장 많이 증가된 값으로 초기화.

다시 카운트..... 

 

2중 for문을 안쓰니 생각보다 어려웠습니다. 푸는데 2시간 정도 걸린 것 같습니다.

 

 

 

 

 

결과

 

https://app.codility.com/demo/results/trainingCBMS42-7B8/

 

 

 

 

 

소스코드

#include <stdlib.h>

void arrInput(int * arr, int num, int len);

struct Results solution(int N, int A[], int M) {
    struct Results result;
    int i, count = 0, max = 0, index = 0, flag = 0;
    int *arr = (int *)malloc(sizeof(int) * N);

    result.L = N;
    arrInput(arr, 0, N);

    for (i = 0; i < M; i++) {     //여기 for문은 max 값과 index 값을 구하기 위한 부분

        if (A[i] > N) {
            max = count;
            index = i;
            flag = 1;
            continue;
        }

        if (flag == 1 && arr[A[i] - 1] < max)
            arr[A[i] - 1] = max;

        arr[A[i] - 1]++;

        if (arr[A[i] - 1] > count)
            count = arr[A[i] - 1];
    }

    if (flag == 0)
        result.C = arr;
    else {
        arrInput(arr, max, N);               //max 값과 index 값을 대입하여 배열을 마무리
        for (i = index + 1; i < M; i++)      //남은 요소 값들 증가
            arr[A[i] - 1]++;

        result.C = arr;
    }

    return result;
}

void arrInput(int * arr, int num, int len) {
    int i;

    for (i = 0; i < len; i++)
        arr[i] = num;
}
​

 

 

처음엔 2중 for문으로 간단히 작성했지만 77점이 나와 다르게 생각하느라 좀 시간이 걸렸던 것 같습니다.

 

처음 시작되는 for문은 max 값과 index 값을 구하는 구간 입니다.

 

N보다 큰 값이 중간 중간 5개 이상 있다고 가정을 하고 N값이 클 때마다 max 값을 업데이트 시켰습니다.

 

하지만 초기화가 되면 (만약 가 있고 N보다 큰 값을 만나 로 됬을 경우)

 

0 값이 4가 되버리니깐 이상황에서 카운터를 다시 세야 했습니다.  때문에 if문을 둬서 max 값보다 arr[] 배열 요소 값이

 

작으면 max 값으로 초기화를 하고 카운터를 셌습니다.

 

index 값은 배열 요소 중 마지막으로 큰 값이 나온 index값을 구하기 위해 코드에 넣었고.

 

index값 이후로는 전혀 큰 값이 나오지 않은 것임으로

 

index 값을 기준으로 max값으로 배열을 초기화 시키고 나머지 배열 요소들을 증가시켜 마무리 지었습니다.

 

 

 

사실 이걸 말로 설명하려고 하니 어렵내요 참...... 코드를 봐도 잘 짠 코드 같지 않아보이고......

 

실력이 참 많이 부족한 것 같습니다.....