/*

코딩테스트 연습 > 코딩테스트 입문 >  중앙값 구하기 문제입니다. 
제 컴퓨터에서 gcc로 컴파일하면 잘 실행됩니다. 
프로그래머스에서 실행하면 결과가 계속 달라져요. 
어떨때는 정답, 어쩔때는 오답입니다.
랜덤함수가 없는데 왜 그런지도 모르겠어요.

< 문제 설명 >
중앙값은 어떤 주어진 값들을 크기의 순서대로 정렬했을 때 
가장 중앙에 위치하는 값을 의미합니다. 
예를 들어 1, 2, 7, 10, 11의 중앙값은 7입니다. 
정수 배열 array가 매개변수로 주어질 때, 중앙값을 return 하도록 solution 함수를 완성해보세요.

< 제한사항 >
1) array의 길이는 홀수입니다.
2) 0 < array의 길이 < 100
3) -1,000 < array의 원소 < 1,000

< 입출력 예 >
array = {1, 2, 7, 10, 11}   =>   result = 7
array = {9, -1, 0}          =>   result = 0

*/

#include <stdio.h>
#include <stdlib.h>

int solution(int* array, int array_len)
{
    int n = array_len / 2 + 1;                 // array의 중앙의 위치, rank의 길이
    int* rank = (int*)malloc(n * sizeof(int)); // 큰 원소부터 정렬

    for(int i = 0; i < array_len; i++) // array의 길이만큼 반복
    {
        for(int j = 0; j < n; j++)     // rank의 길이만큼 반복
        {
            if(array[i] > rank[j]) // array[i]가 rank[j]보다 크면
            {
                // rank[j]에 array[i]를 대입하기 위해 빈자리를 만든다
                // k는 (n - 1)부터 (j + 1)까지 반복
                for(int k = n - 1; k > j; k--)
                {
                    rank[k] = rank[k - 1];
                }
                rank[j] = array[i];
                break;
            }
        }
    }

    int answer = rank[n - 1];
    free(rank);

    return answer;
}

int main()
{
    int array1[] = {9, -1, 5};
    printf("{9, -1, 5}, 3 => %d\n", solution(array1, 3));

    int array2[] = {1, 2, 4, 6, 7, 8, 9};
    printf("{1, 2, 4, 6, 7, 8, 9}, 7 => %d\n", solution(array2, 7));

    int array3[] = {1, 7, 2, 11, 10};
    printf("{1, 7, 2, 11, 10}, 5 => %d\n", solution(array3, 5));

    int array4[] = {-3, 5, -5};
    printf("{-3, 5, -5}, 3 => %d\n", solution(array4, 3));

    return 0;
}