프로그래머스 입문 120812 최빈값 구하기

문제

출처

정수 배열이 매개변수로 주어졌을 때 최빈값을 반환해야 한다.
단, 최빈값이 여러 개라면 -1을 반환한다.

배열의 길이는 1 <= array_len < 100이다.
배열 원소의 값은 0 <= array[i] < 1000이다.

array	result
[1]	1
[1, 2, 2]	2
[1, 1, 2, 2, 3]	-1
[1, 2, 3, 3, 3, 4]	3

풀이

정렬 후 연속 개수 세기

#include <stdlib.h>

int compare(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}

int solution(int array[], size_t array_len) {
    qsort(array, array_len, sizeof(int), compare);

    int current_number = array[0];
    int current_frequency = 1;

    int mode_number = array[0];
    int mode_frequency = 0;

    for (size_t i = 1; i < array_len; i++)
    {
        if (current_number == array[i])
        {
            current_frequency++;
            continue;
        }

        if (mode_frequency < current_frequency)
        {
            mode_frequency = current_frequency;
            mode_number = current_number;
        }
        else if (mode_frequency == current_frequency)
        {
            mode_number = -1;
        }

        current_number = array[i];
        current_frequency = 1;
    }

    if (mode_frequency < current_frequency)
    {
        mode_frequency = current_frequency;
        mode_number = current_number;
    }
    else if (current_frequency == mode_frequency)
    {
        mode_number = -1;
    }

    return mode_number;
}

먼저 오름차순으로 배열을 정렬한다.
정렬하면 같은 숫자들이 서로 붙어 있으므로, 연속으로 등장한 횟수만 세면 각 숫자의 등장 횟수를 알 수 있다.
같은 숫자가 이어지면 현재 숫자의 등장 횟수를 계속 늘린다.
다른 숫자가 나오면 지금까지 센 등장 횟수를 기존 최고 등장 횟수와 비교한다.
지금까지 센 등장 횟수가 기존 최고 등장 횟수보다 크면 최빈값과 최고 등장 횟수를 갱신한다.
기존 최고 등장 횟수와 같다면 최빈값이 여러 개라는 뜻이므로 -1로 설정한다.
반복문이 끝났을 때 마지막으로 세던 숫자의 등장 횟수는 아직 최고 등장 횟수와 비교하지 않았으므로 한 번 더 검사한다.

위 코드는 잘 작동하지만 반복문 안과 밖에 같은 검사 코드가 중복된다.
아래 코드는 중복 코드를 없앤 대신 반복문 안에서 매번 최고 등장 횟수보다 큰지, 같은지 검사한다.

#include <stdlib.h>

int compare(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}

int solution(int array[], size_t array_len) {
    qsort(array, array_len, sizeof(int), compare);

    int current_number = array[0];
    int current_frequency = 1;

    int mode_number = array[0];
    int mode_frequency = 1;

    for (size_t i = 1; i < array_len; i++)
    {
        if (current_number == array[i])
        {
            current_frequency++;
        }
        else
        {
            current_number = array[i];
            current_frequency = 1;
        }

        if (mode_frequency < current_frequency)
        {
            mode_frequency = current_frequency;
            mode_number = current_number;
        }
        else if (mode_frequency == current_frequency)
        {
            mode_number = -1;
        }
    }

    return mode_number;
}

값별 빈도 배열로 세기

#include <stddef.h>

int solution(int array[], size_t array_len) {
    int frequency_by_value[1000] = { 0 };

    for (size_t i = 0; i < array_len; i++)
    {
        frequency_by_value[array[i]]++;
    }

    int mode = 0;
    int mode_frequency = frequency_by_value[0];
    int mode_candidate_count = 1;

    for (int i = 1; i < 1000; i++)
    {
        if (frequency_by_value[i] > mode_frequency)
        {
            mode = i;
            mode_frequency = frequency_by_value[i];
            mode_candidate_count = 1;
        }
        else if (frequency_by_value[i] == mode_frequency)
        {
            mode_candidate_count++;
        }
    }

    if (mode_candidate_count >= 2)
    {
        return -1;
    }

    return mode;
}

앞선 코드는 배열을 먼저 정렬해야 사용할 수 있었다.
이번에는 정렬 여부와 상관없이 최빈값을 구하는 방법을 시도해 본다.
다만, 이 방법은 문제에서 원소 값의 범위가 0 이상 999 이하로 제한되어 있기 때문에 사용할 수 있다.

매개변수로 들어온 array 배열의 값을 인덱스로 삼아 frequency_by_value에 등장 횟수를 세어 둔다.
array 배열에서 1이라는 값이 2번 등장했다면 frequency_by_value[1] == 2가 된다.
array 배열에서 2라는 값이 3번 등장했다면 frequency_by_value[2] == 3이 된다.

최빈값을 구하려면 후보 값을 저장할 변수도 필요하지만, 실제 최빈값인지 확인하려면 등장 횟수도 함께 비교해야 한다.
mode는 최빈값 그 자체이다.
mode_frequency는 최빈값이 몇 번 등장했는지를 의미한다.
mode_candidate_count는 최고 등장 횟수를 가진 값이 몇 개인지를 기록한다.

이제 반복문을 돌면서 더 큰 등장 횟수를 만나면 최빈값과 최고 등장 횟수를 갱신한다.
새로운 최고 등장 횟수가 나왔으므로 최빈값 후보 수는 1개가 된다.
현재 값의 등장 횟수가 최고 등장 횟수와 같으면 동률이 있다는 뜻이므로 최빈값 후보 수를 증가시킨다.
반복문이 끝난 후 최빈값 후보가 2개 이상이면 -1을 반환하고, 아니라면 최빈값을 반환한다.