[C/C++] 프로젝트 오일러 #22 : 이름 점수 구하기

이 문제에서는 주어진 텍스트 파일에 포함된 이름들의 점수 합계를 계산하는 것을 요구합니다. 문제를 해결하기 위한 단계는 다음과 같습니다:
1. 입력 파일 읽기: 파일에서 각각의 이름이 큰따옴표로 묶여 있는 쉼표로 구분된 단일 행 데이터를 읽습니다.
2. 이름을 알파벳 순으로 정렬: 이름 리스트를 알파벳 오름차순으로 정렬합니다.
3. 이름 점수 계산:
• 각 이름의 점수를 계산합니다. 이름의 점수는 이름을 구성하는 각 글자의 알파벳 값을 더하여 구합니다 (A=1, B=2, …, Z=26).
• 해당 이름 점수에 정렬된 순서(1부터 시작하는 인덱스)를 곱합니다.
4. 전체 점수 계산: 모든 이름 점수를 합산하여 최종 결과를 구합니다.

예를 들어, 파일에 "COLIN", "ALEX", "BOB"가 포함되어 있다면, 정렬된 순서는 "ALEX", "BOB", "COLIN"입니다. "COLIN"의 알파벳 값이 53이고, 순서가 3이라면, 이 점수는  $53\times 3=159$ 입니다.

 

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

 

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

 

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

 

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

 

그러다보니까, 프로그램 자체는 어려울 것이 특별하게 없습니다.

 

name scores

 

여기에 소스를 올립니다.

//------------------------------------------------
//    Project Euler #22 - Names Scores
//        - by Aubrey Choi
//        - created at 2015-01-25
//------------------------------------------------
#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);
    }
}