[Brute Force - 순열] 단어 수학

예제 입력 1

2

AAA

AAA

예제 출력 1

1998

예제 입력 2

2

GCF

ACDEB

예제 출력 2

99437

예제 입력 3

10

A

B

C

D

E

F

G

H

I

J

예제 출력 3

45

예제 입력 4

2

AB

BA

예제 출력 4

187

 

https://www.acmicpc.net/problem/1339

 

- 이것 역시 최대값을 구하는 문제이기 때문에, 등장하는 알파벳 개수에 따라 9 ~ 0만 사용한다. 예를 들어, 등장하는 알파벳 개수가 4개라면, 숫자는 9,8,7,6 만 사용하면 된다.

 

- 등장하는 최대 알파벳의 개수가 10이므로, 10!의 시간복잡도이므로, 배열의 인덱스를 순열로 돌려서 모든 경우에 대해 다 해볼 수 있다. 

 

#include <stdio.h>
#define MAX_WORD_SIZE (9)
#define MAX_DATA_COUNT (10)

#define MAX(a,b) ((a)>(b)?(a):(b))

int N;
char arr[MAX_DATA_COUNT][MAX_WORD_SIZE];
bool alphaCheck[26];

class WordToNum
{
public:
	char item[26];
	int size;
	int weight[10];
	int indexer[10];
	int alphaOrder[26];

	WordToNum()
	{
		size = 0;
		for (int i = 0; i < 10; i++)
		{
			weight[i] = 9 - i;
			indexer[i] = i;
		}

		for (int i = 0; i < 26; i++) alphaOrder[i] = 0;
	}

	void initIndexer()
	{
		for (int i = 0; i < 10; i++) indexer[i] = i;
	}

	void addWord(char item)
	{
		this->item[size] = item;
		alphaOrder[item - 'A'] = size;	// 지금 들어온 알파벳이 몇번째 순서인지? 
										// 입력은 순서대로 들어올거다.
		size++;
	}

	bool next_permutation()
	{
		int i = size - 1;
		while ((i > 0) && (indexer[i - 1] > indexer[i])) i--;

		if (i <= 0) return false;

		int j = size - 1;
		while ((i < j) && (indexer[i - 1] > indexer[j])) j--;

		swap(indexer, i - 1, j);
		j = size - 1;

		while (i < j)
		{
			swap(indexer, i, j);
			i++; j--;
		}

		return true;
	}

	int getSum(char* item)
	{
		int idx = 0;
		int result = 0;

		while (item[idx] != '\0')
		{
			result *= 10;

			// A D E Z
			// item[idx]가 몇번째 알파벳인지?
			int order = alphaOrder[item[idx] - 'A'];


			result += (weight[indexer[order]]);
			idx++;
		}

		return result;
	}

private:
	void swap(int* arr, int a, int b)
	{
		char temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
};
WordToNum w;


int main(void)
{
	scanf("%d", &N);

	for (register int i = 0; i < N; i++)
	{
		scanf("\n%s", arr[i]);

		int idx = 0;
		while (arr[i][idx] != '\0')
		{
			alphaCheck[(arr[i][idx] - 'A')] = true;
			idx++;
		}
	}

	int order = 0;
	for (int i = 0; i < 26; i++)
	{
		if (alphaCheck[i])
		{
			w.addWord(i + 'A');
		}
	}

	int result = 0;

	do
	{
		int nowResult = 0;

		for (int k = 0; k < N; k++)
		{
			nowResult += w.getSum(arr[k]);
		}

		result = MAX(result, nowResult);
	} while (w.next_permutation());

	printf("%d\n", result);
	
	return 0;
}

 

[ C# 6.0 ]

using System;
using System.Collections.Generic;

class Program
{
    public class Word
    {
        public List<string> wordArr = new List<string>();
        public List<int> wordOrder = new List<int>();

        private List<int> numbers = new List<int>();
        private List<int> indexer = new List<int>();

        public Word()
        {
            for (int i = 0; i < 26; i++) wordOrder.Add(-1);
        }

        public long getSum()
        {
            long result = 0;
            
            foreach(string s in wordArr)
            {
                int nowResult = 0;

                foreach(char c in s)
                {
                    nowResult *= 10;
                    nowResult += numbers[indexer[wordOrder[c - 'A']]];
                }

                result += nowResult;
            }

            return result;
        }

        public void updateIndexer()
        {
            int counter = 0;

            for(int i = 0; i < wordOrder.Count; i++)
            {
                if(wordOrder[i] != -1)
                {
                    indexer.Add(counter);
                    numbers.Add(9 - counter);

                    counter++;
                }
            }
        }

        public bool next_permutation()
        {
            int i = indexer.Count - 1;
            while ((i > 0) && (indexer[i - 1] > indexer[i])) i--;

            if (i <= 0) return false;

            int j = indexer.Count - 1;
            while ((i <= j && (indexer[i - 1] > indexer[j]))) j--;

            swap(indexer, i - 1, j);

            j = indexer.Count - 1;
            while((i < j))
            {
                swap(indexer, i, j);
                i++; j--;
            }

            return true;
        }

        private void swap(List<int> arr, int a, int b)
        {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

    static void Main(string[] args)
    {
        Word word = new Word();
        
        string input;
        input = Console.ReadLine();

        int N = Int32.Parse(input);

        int wordCounter = 0;
        for(int i = 0; i < N; i++)
        {
            input = Console.ReadLine();
            word.wordArr.Add(input);

            foreach(char c in input)
            {
                if(word.wordOrder[c - 'A'] == -1)
                    word.wordOrder[c - 'A'] = wordCounter++;
            }
        }

        word.updateIndexer();

        long result = 0;
        do
        {
            result = Math.Max(result, word.getSum());

        } while (word.next_permutation());

        Console.WriteLine(result);
    }
}