BOJ) 단어 수학

단어 수학

1339번: 단어 수학

풀이

 

N개의 단어를 각각 숫자로 바꿔서 모두 더한 값 중 최대값이 되는 경우를 출력한다.

이 때, 단어에 포함되는 알파벳의 갯수는 10개 이하이며, 0~9 사이의 값을 적절하게 배치했을 때의 최대값을 구하는 문제다.

 

처음에는 각 알파벳이 가질 수 있는 값의 모든 경우의 수를 DFS를 통해 저장했다.

입력 받을 때, HashMap에 각 char의 index를 저장하는 식으로 문제를 풀었는데, 메모리와 시간이 매우 비효율적이었다.

생각 덜하고 빠르게 풀려고 코드를 짰다가, 되려 코드가 길어지고 비효율적인 코드를 짜버렸다.

 

코드 1

왠만하면 넘어가는데, 이 정도 결과는 도저히 참고 넘길 수 없었다.

그래서 효율적인 방법이 없을까 생각했다.

 

입력받는 알파벳에 대해 HashMap으로 접근하는 것이 아닌, 배열에 저장하는 것으로 생각했다.

A가 0 ~ Z가 25의 인덱스를 갖는 배열을 선언해줬다.

그리고, 모든 단어를 돌면서 각 자리가 갖는 갯수를 세주었다.

 

for(int j=0; j<len; j++) {
	alphabets[wordArr[j]-A] += Math.pow(MAX, len-j-1);
}

 

 

 

 

각 알파벳의 자릿수 차이를 표현하기 위해 10의 n 승으로 저장해줬다.

제일 첫번째 오는 알파벳은 10^(len-1)의 값을 갖는 카운트인 의미로 저장해줬다.

 

그리고 이렇게 저장된 알파벳을 정렬해주어, 가장 많은 count를 갖는 수부터 for문을 통해 9를 차지하게 답을 구해줬다.

for문이 9~0까지 10번만 도는 이유는 이용되는 알파벳의 갯수가 최대 10이기 때문이다.

 

 

코드 2

마음이 편해졌다.

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class Main {
    final static int MAX = 10;
    static HashMap<Character, Integer> wordMap;
    static ArrayList<int[]> wordNumList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[][] wordArr = new char[n][];
        wordMap = new HashMap<>();
        int wordIdx =0;

        for(int i=0; i<n; i++) {
            wordArr[i] = br.readLine().toCharArray();
            for(int j=0; j<wordArr[i].length; j++) {
                if(!wordMap.containsKey(wordArr[i][j])) {
                    wordMap.put(wordArr[i][j], wordIdx++);
                }
            }
        }
        br.close();
        solution(wordArr);
    }

    private static void solution(char[][] wordArr) {
        int answer =0;
        wordNumList = new ArrayList<>();
        setWordNumList(new boolean[MAX], new ArrayList<>());

        for(int[] numArr : wordNumList) {
            int sum =0;
            for(char[] words : wordArr) {
                sum += getNum(numArr,words);
            }
            answer = Math.max(sum,answer);
        }

        System.out.println(answer);
    }

    private static int getNum(int[] numArr, char[] words) {
        int result =0;
        for(char ch : words) { result = result*MAX + numArr[wordMap.get(ch)]; }
        return result;
    }

    private static void setWordNumList(boolean[] visit, ArrayList<Integer> numList) {
        if(numList.size() ==wordMap.size()) {
            int n = wordMap.size();
            int[] tmp = new int[n];
            for(int i=0; i<n; i++) {
                tmp[i] = numList.get(i);
            }
            wordNumList.add(tmp);
            return;
        }
        for(int i=0; i<MAX; i++) {
            if(!visit[i]) {
                visit[i] = true;
                numList.add(i);
                setWordNumList(visit, numList);
                numList.remove(numList.size()-1);
                visit[i] = false;
            }
        }
    }
}

 

코드 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    final static int MAX = 10, MAX_ALPHABET = 26;
    final static char A = 'A';

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] alphabets = new int[MAX_ALPHABET];

        for(int i=0; i<n; i++) {
            char[] wordArr = br.readLine().toCharArray();
            int len = wordArr.length;
            for(int j=0; j<len; j++) {
                alphabets[wordArr[j]-A] += Math.pow(MAX, len-j-1);
            }
        }
        br.close();
        solution(alphabets);
    }

    private static void solution(int[] wordArr) {
        int answer =0;
        Arrays.sort(wordArr);
        int idx = MAX_ALPHABET-1;
        for(int i=MAX-1; i>=0; i--) {
            answer += wordArr[idx--] * i;
        }
        System.out.println(answer);
    }
}