Codility - MaxCounters

문제)

설명

N = 리턴할 배열의 크기

A[] = 문제의 배열 요소

M = A[] 배열의 크기

 

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

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

 

예시

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

    A[M]                        Arr[N]

A[0] = 3                    {0, 0, 1, 0, 0}

A[1] = 4                    {0, 0, 1, 1, 0}

A[2] = 4                    {0, 0, 1, 2, 0}

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

A[4] = 1                    {3, 2, 2, 2, 2}

A[5] = 4                    {3, 2, 2, 3, 2}

A[6] = 4                    {3, 2, 2, 4, 2}

 

리턴 값은 {3, 2, 2, 4, 2} 가 저장된 배열 주소 값.

 

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

 

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

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

다시 카운트..... 

 

소스 코드

#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 값을 업데이트 시켰습니다.

하지만 초기화가 되면 (만약 {0, 1, 4, 4, 2} 가 있고 N보다 큰 값을 만나 {4, 4, 4, 4, 4}로 됬을 경우)

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

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

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

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

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

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

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