BOJ_1339 : 단어 수학

👉 문제링크

---

---

🔸 문제 분석 🔸

• N개의 단어가 주어진다. 단어는 알파벳으로 구성되어 있는데, 각 알파벳은 0~9 숫자로 변환할 수 있다.
• 알파벳은 최대 10종류가 주어지고, 알파벳의 숫자는 겹치지 않아야 한다.
• N개의 단어를 숫자로 변환했을 때 총합의 최대값을 출력한다.

🔸 문제 풀이 🔸

• 각 알파벳이 어떤 숫자와 매칭 되어야 최대값이 되는지 찾는 문제이다.
• Brute Force로 전부 넣어봐도 찾을 수 있지만, 좀더 효율적으로 찾고자 각 알파벳 별 가중치를 계산한다.
• 가중치 순서대로 9부터 0까지 부여한 후 값을 계산해 출력한다.

🔸 코드 🔸

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

public class Main {

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] alpha_input = new int[26]; // 입력 된 알파벳 별 가중치

        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            char[] chars = temp.toCharArray();

            // 가중치 저장
            int len = (int) Math.pow(10, temp.length() - 1);
            for (char c : chars) {
                alpha_input[c - 'A'] += len;
                len /= 10;
            }
        }

        // Sort
        Arrays.sort(alpha_input);

        // Output
        int sum = 0;
        int num = 9;
        for (int i = 25; i >= 15; i--) {
            sum += alpha_input[i] * num--;
        }
        bw.write(Integer.toString(sum));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 입력된 문자의 자릿수 가중치를 alpha_input[] 배열에 누적한다.
• 가중치 순서대로 오름차순 정렬한다.
• 뒤에서부터 큰 가중치 순으로 9부터 0까지 부여하며 값을 누적한다.

---

🔸 end 🔸

• Brute Force 로 찾는 법은 바로 생각했지만, 너무 비효율적인 것 같아서 다른 방법을 찾고자 했다.
  • 가중치를 저장은 했지만, 값을 계산할 때 문자의 길이 순으로 숫자를 부여해서 틀렸다.
  • 단어의 길이가 1씩, 같은 문자로 이루어진 여러 단어가 주어지는 경우가 대표적인 반례였다.
• 결국 길이로 숫자를 부여하는게 아니라, 가중치 별로 숫자를 부여했다.
  • 기존의 코드를 지우기만 해서 정답을 맞출 수 있었다.
  • 너무 어렵게 생각했던 것 같다.