22. 프로젝트 오일러 #22 : 이름 점수 구하기

이번 문제는 이름 점수를 구해서 정렬한 순서값을 곱하는 비교적 간단한 알고리즘입니다.

정렬이야 원래 C/C++ 에 들어가 있는 qsort()를 써도 되고, 아주 간단한 알고리즘을 적용해도 그다지 큰 문제가 없습니다.

저는 힙정렬을 만들어서 짜보았습니다.  힙정렬이 베스트라고는 할 수는 없지만, 처음에는 파일로 읽어서 사용할 예정이었기 때문에, 힙정렬이나 삽입정렬이 그런면에서는 유리한 점이 있습니다.  다른 정렬은 모두 배열에 일단 넣고, 그 다음 정렬을 하게 되지만, 힙정렬이나 삽입정렬은 삽입을 비교적 다른 정렬 방법에 비해서 손쉽게 할 수 있는 장점이 있습니다.  정렬 과정에서 삽입과정이 일어나니까요.

주어진 데이터 파일을 보니, 파싱보다는 그냥 소스에 붙여넣기 또는 #include "names.txt"를 이용해서 넣는 것이 유리하게 되어있네요.  쌍따옴표로 묶여있고, 콤마로 분리되어 있으니, 굳이 파일을 읽어서 파싱을 할 이유는 없었습니다.

그러다보니까, 프로그램 자체는 어려울 것이 없었네요.

여기에 소스를 올립니다.

#include <stdio.h>
#include <string.h>

void heapsort(const char *array[], int n);
const char *getfirst(const char *array[], int *n);
int getvalue(const char *str);

int main()
{
    const char *names[] = {
        #include "names.txt"
    };

    int n = sizeof(names)/sizeof(const char *);

    heapsort(names, n);

    int sum = 0, s = 1;
    while( n )
    {
        const char *p = getfirst(names, &n);
        sum += getvalue(p) * s++;
    }

    printf("Ans = %d\n", sum);
}

void heapify(const char *arrary[], int n, int k);

void heapsort(const char *array[], int n)
{
    for( int i = n/2-1 ; i >= 0 ; i-- )
    {
        heapify(array, n, i);
    }
}

const char *getfirst(const char *array[], int *pn)
{
    int n = --(*pn);
    const char *ret = array[0];
    array[0] = array[n];
    heapify(array, n, 0);
    return ret;
}

int getvalue(const char *str)
{
    int v = 0;
    while( *str ) v += *str++ - 'A' + 1;
    return v;
}

void heapify(const char *array[], int n, int k)
{
    int l = k*2+1, r = k*2+2;
    int m = l;
    if( l >= n ) return;
    if( r < n && strcmp(array[l], array[r]) > 0 ) m = r;
    if( strcmp(array[k], array[m]) > 0 )
    {
        const char *t = array[k];
        array[k] = array[m];
        array[m] = t;
        heapify(array, n, m);
    }
}