[백준] 단어 수학(1339) Java

문제 링크

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

1339번: 단어 수학

 

문제 요약

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

 

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

 

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

 

접근법

제한시간이 2초이고, 단어의 개수가 최대 10개, 알파벳 개수도 최대 10개, 수의 최대 길이는 8개이므로

브루트포싱으로 충분히 풀 수 있을 거라고 보였다.

 

혹시나 해서 브루트포싱을 했을 때 시간복잡도를 대충 계산해보면,

10개의 알파벳에 10개의 숫자를 대입하는 경우, 즉 10개의 숫자를 배열하는 모든 경우의 수 이므로

10! = 3,628,800 경우의 수만 확인해 주면 된다.

 

각 경우마다 단어의 합을 구한 뒤 그 최대값을 구하는게 목표인데, 단어의 합을 구하는 데 드는 시간 복잡도를 대충 계산해보면

길이 8의 단어가 10개 있다고 했을 때 80번의 반복이면 단어의 합을 구할 수 있다.

 

따라서 이 정도의 시간복잡도면 브루트포싱으로 충분히 가능할 거라고 생각을 하고 풀어봤는데

시간 초과는 안 뜨는데 걸리는 시간이 2400ms 정도로 매우 오래 걸렸다.

 

그래서 그리디 알고리즘을 사용해서 접근해보려고 했는데,

나는 그리디 알고리즘이라고 풀고 있었는데 다 짜고 보니까 그냥 수식을 만들어서 푸는 접근법과 동일했다.

 

자세한 것은 아래 링크 참조

https://squareyun.tistory.com/23

[Java] 백준 1339 : 단어 수학

 

 

시간 복잡도

브루트포스: O(N!)

그리디(?): O(N)

 

 

공간 복잡도

단어만 저장하면 되는 정도라서 의미 없음.

 

 

풀면서 놓쳤던 점

문제 분류가 그리디 알고리즘으로 되어있어서, 뭔가 그리디 하게 접근을 한다고 했는데 그 과정에서 실수가 있었다.

 

{AB, B, B, B, B, B, B, B, B, B} 이런 10개의 단어가 주어졌을 때,

A = 9, B = 8을 대입한 결과와 B = 9, A = 8을 대입한 결과가 170으로 동일하다 (98 + 8 * 9 == 89 + 9 * 9)

 

그런데 나는 머릿속으로만 생각하다 보니 전자의 값이 더 크다고 잘못 생각했다.

 

여기서 매우 큰 문제가 생겼는데,

자리수가 더 높을 수록 더 높은 숫자를 부여 받는 우선순위가 있는 것은 자명하다.

근데 그 우선순위를 값으로 표현할 때,

1의 자리의 우선순위는 1, 10의 자리의 우선순위는 10 이런 식으로 10배 차이나게 표현하면 나의 잘못된 전제와는 모순이 생겨버린다.

(어차피 잘못된 전제이므로 자세히 설명하지는 않겠다)

 

그래서 자리수에 따른 우선순위의 배율을 10배가 아닌 12배로 해서 코드를 짰더니 틀렸다.

그래서 혹시나 하는 마음에 10배로 바꿔 봤더니 바로 맞아서, 내 전제가 틀렸다는 것을 그때야 다시 확인하면서 알았다.

 

근데 이렇게 어렵게 접근할 문제가 아닌게,

위에서 참고하라고 해 놓은 링크를 보면 그냥 자릿수에 따라 가중치를 주고, 가중치가 높은 숫자에 그냥 높은 숫자를 부여해서 답을 구하면 끝난다. 무슨 무슨 알고리즘 이렇게 보는 것이 아니라 그냥 직관적으로 생각해서 풀면 풀리는 문제였던 것.

 

열심히 풀었는데 조금 아쉽다 ㅋㅋ....

 

 

이 문제에서 얻어갈 점

브루트포싱할 때 HashMap을 사용했다.

 

 

코드 - 브루트포스 버전

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numOfWords;
        numOfWords = Integer.parseInt(br.readLine());

        ArrayList<String> wordList = new ArrayList<>(numOfWords);
        for (int i = 0; i < numOfWords; i++)
            wordList.add(br.readLine());

        //브루트포싱을 편하게 하기 위해 알파벳-숫자 에 대한 map을 사용
        HashMap<Character, Integer> alphaNumMap = new HashMap<>(10);
        //word에 들어있는 모든 알파벳을 저장하는 arraylist
        //이 list를 탐색하면서 재귀함수를 호출 할 것이다
        ArrayList<Character> alphaList = new ArrayList<>(10);

        //word에 들어있는 모든 알파벳을 map에 넣어준다. 숫자는 임의의 값인 0으로 초기화.
        setAlphaNumMap(alphaNumMap, wordList);
        alphaList.addAll(alphaNumMap.keySet()); //알파벳을 list로 저장

        //재귀함수를 돌면서 브루트포싱을 할 때 이미 알파벳에 부여한 숫자는 넘어가야 함
        //그 것을 위해 사용할 배열. 0-9까지의 index는 숫자 0-9를 의미
        boolean[] usedNumArr = new boolean[10];

        System.out.println(
                getMaxValue(alphaList, alphaNumMap, wordList, usedNumArr, 0));
    }

    static int getMaxValue(ArrayList<Character> alphaList, HashMap<Character, Integer> alphaNumMap,
                           ArrayList<String> wordList, boolean[] usedNumArray, int alphaIdx)
    {
        int maxVal = 0;

        //숫자를 전부 대입했을 경우 단어의 합을 구한다
        if (alphaIdx == alphaList.size())
            return getWordSum(alphaNumMap, wordList);

        //현재 알파벳 (alphaIdx에 해당하는 알파벳)에, 아직 대입하지 않은 숫자를 0부터 10까지 탐색하면서
        //하나씩 대입하며 재귀호출을 함
        for (int num = 0; num < 10; num++)
        {
            //이전의 재귀 호출에서 대입한 숫자는 넘어감
            if (usedNumArray[num])
                continue;

            usedNumArray[num] = true;

            //map에 알파벳-숫자를 넣어줌
            alphaNumMap.put(alphaList.get(alphaIdx), num);
            maxVal = Math.max(maxVal,
                    getMaxValue(alphaList, alphaNumMap, wordList, usedNumArray, alphaIdx + 1));

            usedNumArray[num] = false;
        }

        return maxVal;
    }

    static int getWordSum(HashMap<Character, Integer> alphaNumMap, ArrayList<String> wordList)
    {
        int sum = 0;
        int digit = 1;

        for (String word : wordList)
        {
            for (int i = word.length() - 1; i >= 0; i--)
            {
                sum += alphaNumMap.get(word.charAt(i)) * digit;
                digit *= 10;
            }
            digit = 1;
        }

        return sum;
    }

    static void setAlphaNumMap(HashMap<Character, Integer> alphaNumMap, ArrayList<String> wordList)
    {
        for (String word: wordList)
        {
            for (int i = 0; i < word.length(); i++)
                alphaNumMap.put(word.charAt(i), 0);
        }

    }
}

 

코드 - 그리디(?) 버전

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numOfWords;
        numOfWords = Integer.parseInt(br.readLine());

        ArrayList<String> wordList = new ArrayList<>(numOfWords);
        for (int i = 0; i < numOfWords; i++)
            wordList.add(br.readLine());

        //알파벳과 그 알파벳의 priority를 저장해 둔 배열
        //priority값이 클 수록 더 높은 숫자를 배정받는다
        Alphabet[] alphaArr = new Alphabet[26];
        for (int i = 0; i < 26; i++)
            alphaArr[i] = new Alphabet((char)('A' + i));

        //wordList를 탐색하며 각 알파벳의 priority를 구한다
        getAlphabetPriority(alphaArr, wordList);

        //priority 값이 큰 순서대로 알파벳을 정렬
        Arrays.sort(alphaArr, Comparator.reverseOrder());

        System.out.println(getWordSum(alphaArr, wordList));

        br.close();
    }

    //알파벳의 priority를 구하는 함수
    static void getAlphabetPriority(Alphabet[] alphaArr, ArrayList<String> wordList)
    {
        int priority = 1;

        //1의 자리의 priority는 1, 10의 자리의 priority는 10
        //이것을 모든 word의 알파벳에 대해 누적해준다
        for (String word: wordList)
        {
            for (int i = word.length() - 1; i >= 0; i--)
            {
                alphaArr[word.charAt(i) - 'A'].priority += priority;
                priority *= 10;
            }
            priority = 1;
        }
    }

    //단어의 합을 구하는 함수
    static int getWordSum(Alphabet[] alphaArr, ArrayList<String> wordList)
    {
        int sum = 0;
        int digit = 1;

        int[] alphaNum = new int[26];

        //priority가 큰 순서대로 알파벳에 9부터 0까지의 수를 부여한다
        for (int i = 0; i <= 9; i++)
            alphaNum[alphaArr[i].alphabet - 'A'] = 9 - i;

        //부여한 값을 가지고 단어의 합을 계산한다
        for (String word : wordList)
        {
            for (int i = word.length() - 1; i >= 0; i--)
            {
                sum += alphaNum[word.charAt(i) - 'A'] * digit;
                digit *= 10;
            }
            digit = 1;
        }

        return sum;
    }
}

class Alphabet implements Comparable<Alphabet>
{
    char alphabet;
    int priority;

    Alphabet(char alphabet)
    {
        this.alphabet = alphabet;
        this.priority = 0;
    }

    public int compareTo(Alphabet o)
    {
        return Integer.compare(this.priority, o.priority);
    }
}