백 준 - 1339

문제 : www.acmicpc.net/problem/1339

1339번: 단어 수학

 

문제는 다음과 같습니다.

 

문제에서 요구하는 것은 대문자 알파벳으로 이루어진 문자열의 갯수가 주어지면 알파벳을 0에서 9 사이의 값으로 설정해서 더한 값에서 최댓값을 구하는 것입니다.

 

여기서 입력의 조건을 보시면 모든 단어에 포함되어 있는 알파벳은 최대 10개로 하였으므로 저희는 주어진 알파벳을 0 ~ 9 사이로 중복없이 배정하고 값을 더해주면 됩니다.

 

따라서 순열을 이용해서 구현해보도록 하겠습니다.

순열을 구현한 코드는 다음과 같습니다.

 // 순열로 모든 경우를 파악
    public static void permutation(LinkedList<Integer> values , boolean[] flag , List<Character> chars , int offset) {

        if (isCheck(flag)) {

            return;
        }

        for (int i = 0 ; i < flag.length ; i++) {

            if(flag[i] == false) {

                flag[i] = true;
                values.add(i + offset);

                permutation(values , flag , chars , offset);

                flag[i] = false;
                values.removeLast();

            }
        }

    }
    
    
    public static boolean isCheck(boolean[] flag) {

        for(int i = 0 ; i < flag.length ; i++) {

            if (flag[i] == false) {

                return false;
            }
        }

        return true;
    }
}

 

길이가 10인 flag 배열을 이용해서 해당 값이 이전에 선택되었는가를 판단하고 선택이 안되어있으면 추가해줍니다. 그런 다음에 10개 모두 추가되어서 완성이 된 경우에 저희가 원하는 처리 if(isCheck(flag)) 안에서 구현하면 됩니다.

 

전체적인 코드는 다음과 같습니다.

import java.util.*;

public class Main {

    // 문제 1339

    public static HashMap<Character , Integer> map = new HashMap<>();
    public static List<String> strs = new ArrayList<>();

    public static int maxValue = -1;

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);

        int k = stdin.nextInt();

        stdin.nextLine();

        HashSet<Character> set = new HashSet<>();

        for (int i = 0 ; i < k ; i++) {

            String line = stdin.nextLine();
            strs.add(line);

            for (int j = 0 ; j < line.length() ; j++) {

                char ch = line.charAt(j);

                set.add(ch);
            }
        }

        ArrayList<Character> chars = new ArrayList<>();

        Iterator<Character> itr = set.iterator();
        while(itr.hasNext()) {

            chars.add(itr.next());
        }

        LinkedList<Integer> values = new LinkedList<>();
        boolean[] flag = new boolean[set.size()];

        int offset = 10 - set.size();

        permutation(values , flag , chars , offset);


        System.out.println(maxValue);
    }

    // string to integer value
    public static int convert(String str) {

        int val = 0;
        int mul = 1;

        for(int i = str.length() - 1 ; i >= 0 ; i--) {

            char ch = str.charAt(i);
            int num = map.get(ch) * mul;

            val += num;

            mul *= 10;
        }

        return val;
    }


    // permute all possible condition
    public static void permutation(LinkedList<Integer> values , boolean[] flag , List<Character> chars , int offset) {

        if (isCheck(flag)) {

            map.clear();

            for (int i = 0 ; i < chars.size() ; i++) {

                map.put(chars.get(i) , values.get(i));
            }

            int sum = 0;

            for (int j = 0 ; j < strs.size() ; j++) {

                int val = convert(strs.get(j));

                sum += val;
            }


            if (maxValue < sum) {

                maxValue = sum;
            }

            return ;
        }

        for (int i = 0 ; i < flag.length ; i++) {

            if(flag[i] == false) {

                flag[i] = true;
                values.add(i + offset);

                permutation(values , flag , chars , offset);

                flag[i] = false;
                values.removeLast();

            }
        }

    }


    public static boolean isCheck(boolean[] flag) {

        for(int i = 0 ; i < flag.length ; i++) {

            if (flag[i] == false) {

                return false;
            }
        }

        return true;
    }
}