[C/C++] 프로젝트 오일러 #98 Anagramic Squares(완전 탐색)

Project Euler 문제 98번은 “아나그램 수의 쌍”에 관한 문제입니다. 문제는 다음과 같은 상황을 제시합니다.

먼저, 아나그램이란 한 단어의 문자들을 재배열하여 다른 단어를 형성하는 것을 말합니다. 예를 들어, “LISTEN”과 “SILENT”은 서로 아나그램입니다. 이 문제에서는 단어 목록이 제공되며, 이 목록에서 아나그램 쌍을 찾아야 합니다.

여기에서 한 걸음 더 나아가, 아나그램 쌍에 특정 조건을 부과합니다. 각 아나그램 단어 쌍에 대해, 이를 숫자로 매핑하여 정사각형 수가 되도록 만들어야 합니다. 예를 들어, “CARE”와 “RACE”가 아나그램이라면, “CARE”를 숫자 1296으로, “RACE”를 숫자 9216으로 매핑했을 때 둘 다 정사각형 수라면 유효한 쌍이 됩니다.

문제는 주어진 단어 목록에서 이 조건을 만족하는 아나그램 단어 쌍을 찾아, 가능한 가장 큰 정사각형 수를 구하는 것입니다.

요약하면, 문제는 아나그램 쌍을 찾고, 이를 숫자로 변환한 뒤 두 숫자가 정사각형 수인지 확인하며, 최댓값을 구하는 것을 요구합니다.

 

anagram

 

제가 작성한 소스는 다음과 같습니다.

 

//------------------------------------------------
//    Project Euler #98 - Image.Resampling.BILINEAR
//        - by Aubrey Choi
//        - created at 2015-10-25
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>

#define    FILENAME    "0098.txt"
const char *words[] = {
#include "0098.txt"
};

int GetSquare(int a, int b, int test[], int v[], int k, int mask)
{
    while( k < 26 && test[k] == 0 ) k++;
    if( k == 26 )
    {
        int numa = 0, numb = 0, sq;
        for( int i = 0, isFirst = 1 ; words[a][i] ; i++, isFirst = 0 ) 
        {
            if( isFirst && v[words[a][i]-'A'] == 0 ) break;
            numa = numa*10 + v[words[a][i]-'A'];
        }
        sq = sqrt((double)numa);
        if( sq == 0 || sq*sq != numa ) return 0;
        for( int i = 0, isFirst = 1 ; words[b][i] ; i++, isFirst = 0 ) 
        {
            if( isFirst && v[words[b][i]-'A'] == 0 ) break;
            numb = numb*10 + v[words[b][i]-'A'];
        }
        sq = sqrt((double)numb);
        if( sq == 0 || sq*sq != numb ) return 0;
        return numa>numb?numa:numb;
    }
    int max = 0;
    for( int i = 0 ; i < 10 ; i++ )
    {
        if( mask & (1<<i) ) continue;
        v[k] = i;
        int ret = GetSquare(a, b, test, v, k+1, mask | (1<<i));
        if( ret > max ) max = ret;
    }
    return max;
}

int GetSquare(int a, int b)
{
    int test[26];
    memset(test, 0, sizeof(test));
    
    for( int i = 0 ; words[a][i] ; i++ ) test[words[a][i]-'A']++;

    int v[26];

    return GetSquare(a, b, test, v, 0, 0);
}

bool IsAnagram(int a, int b)
{
    int test[26];
    memset(test, 0, sizeof(test));
    
    for( int i = 0 ; words[a][i] ; i++ ) test[words[a][i]-'A']++;
    for( int i = 0 ; words[b][i] ; i++ ) test[words[b][i]-'A']--;

    for( int i = 0 ; i < 26 ; i++ ) if( test[i] ) return false;

    return true;
}

void solve1()
{
    int max = 0;
    for( int i = 0 ; i < sizeof(words)/sizeof(char *) ; i++ )
    {
        for( int j = i+1 ; j < sizeof(words)/sizeof(char *) ; j++ )
        {
            if( IsAnagram(i, j) == false ) continue;
            int ret = GetSquare(i, j);
            if( ret > max )
            {
                max = ret;
                printf("%s, %s (%d)\n", words[i], words[j], ret);
            }
        }
    }
    printf("Ans = %d\n", max);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

 

위의 코드는 Project Euler #98 문제를 해결하기 위해 작성된 C 프로그램입니다. 문제의 요구 사항인 “아나그램 단어 쌍을 찾고, 숫자 정사각형 쌍을 계산하여 최대값을 구하는 것”을 해결하는 방식으로 구성되어 있습니다. 아래는 코드의 동작 방식과 주요 부분에 대한 설명입니다.

코드의 해결 방식 설명

 

1. 아나그램 쌍 탐색
주어진 단어 목록에서 모든 가능한 단어 쌍을 확인합니다.
• 두 단어가 아나그램인지 확인하는 IsAnagram 함수가 사용됩니다.
• 이 함수는 각 단어의 알파벳 빈도를 비교하여 동일한 알파벳 구성인지 판별합니다.

 

2. 숫자 매핑 및 정사각형 수 확인
아나그램인 단어 쌍이 발견되면, 각 단어의 알파벳을 숫자로 매핑하여 정수로 변환합니다.
• 변환된 숫자가 정사각형 수인지 확인하는 GetSquare 함수가 사용됩니다.
• 이 과정에서 재귀를 사용하여 가능한 모든 알파벳-숫자 매핑을 시도하며, 유효한 정사각형 수가 나올 때까지 탐색합니다.

 

3. 최대값 계산
모든 아나그램 쌍을 탐색하며 정사각형 수의 최대값을 추적합니다.
• 최대값은 solve1 함수에서 관리하며, 조건을 만족할 때마다 업데이트됩니다.

 

4. 결과 출력 및 실행 시간 계산
가장 큰 정사각형 수와 그에 해당하는 단어 쌍이 출력되며, 실행 시간도 함께 표시됩니다.

코드의 주요 함수 설명

 

1. IsAnagram
• 두 단어가 아나그램인지 확인합니다.
• 각 단어의 알파벳 빈도를 계산한 후, 두 단어의 빈도 배열을 비교합니다.
• 빈도 배열이 동일하면 아나그램으로 판단합니다.

 

2. GetSquare (재귀 함수)
• 아나그램 단어 쌍의 알파벳을 숫자로 매핑하여 정수로 변환합니다.
• 모든 가능한 매핑 조합을 시도하며, 변환된 숫자가 정사각형 수인지 확인합니다.
• 두 단어 모두 정사각형 수로 변환 가능한 경우, 더 큰 값을 반환합니다.

 

3. solve1
• 전체 단어 목록에서 모든 가능한 쌍을 생성하고 탐색합니다.
• 아나그램 쌍을 IsAnagram으로 확인한 뒤, GetSquare로 정사각형 수를 계산합니다.
• 최대값을 찾고 결과를 출력합니다.

 

4. main
• 프로그램 실행의 시작점으로, solve1을 호출하고 실행 시간을 측정합니다.

코드의 구조적 요약
• 입력 데이터: 0098.txt 파일에서 단어 목록을 불러옵니다.
• 핵심 로직: 아나그램 쌍 탐색 -> 숫자 매핑 -> 정사각형 수 확인 -> 최대값 추적.
• 결과 출력: 최대값과 해당 단어 쌍을 출력합니다.