[알고리즘] 중앙값 찾기

배경

문제중 끊어진 그룹 배열/Linked List에서 중앙값(중간값)을 찾아야 하는 경우가 있다.

그룹 배열을 기준으로 작성되었으며 고정으로 10개가 그룹화 되어 있다고 가정하였다.

Idea

그룹 배열이기 때문에 그룹안에 몇개가 있는지 아는 상황이다.

1. 목표하는 숫자에 근접한 그룹을 찾는다.
2. 그룹안에서 딱 맞는 위치의 index를 찾는다.

int sample[3][10] = { 0, };

void Tsample()
{
    int cnt = 1;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 10; j++)
            sample[i][j] = cnt++;
}

void TfindMid_sub(int m)
{
    int sum = 1;
    int i = 0;

    for (; i < 3; i++)
    {
        if (sum + 10 > m) break;

        sum += 10;
    }

    int index = 0;
    while (1)
    {
        if (sum == m) break;

        index++;
        sum++;
    }

    printf("%d\n", sample[i][index]);
}


// 중간 값을 찾는 방법
void TfindMid(int total)
{
    Tsample();

    int m = total / 2;

    if (total % 2 == 0)
    {
        TfindMid_sub(m);
    }
    else
    {
        TfindMid_sub(m);
        TfindMid_sub(m + 1);
    }
}

int main()
{
    //run_test();

    TfindMid(21);

    return 0;
}