[Baekjoon] 1339번: 단어 수학

1339번: 단어 수학

이 문제는 문자의 합이 최대일 경우를 계산하는 그리디 알고리즘 문제였습니다. 저는 이 문제를 다음과 같이 분석했습니다.

1. 각 문자에 해당하는 자릿수(예제 2의 경우 G = 100, C = 10, F = 1)의 값을 int[26]의 알파벳 배열에 저장한다
2. 저장된 배열을 크기순으로 정렬한다
3. 9부터 0까지 내려가며 정렬된 배열의 값과 곱한 값들을 더한 뒤 결과를 출력한다

예제 2를 활용하여 예를 들어보겠습니다. 두 문자열 GCF, ACDEB 가 있습니다. 먼저 GCF부터 값을 구해보도록 하겠습니다. 3자리이므로 각 알파벳은 100, 10, 1을 할당받고 alpha 배열에 더해집니다. 다음은 ACDEB입니다. 5자리이므로 각 알파벳은 10000, 1000, 100, 10, 1을 할당받고 alpha에 더해집니다. 그렇다면 현재 alpha 배열의 상황은 다음과 같습니다(0인 알파벳은 생략했습니다).

 

A: 10000

B: 1

C: 10 + 1000 = 1010

D: 100

E: 10

F: 1

G: 100

 

그리고 이 배열을 크기 순으로 정렬합니다. 합계를 구하는 것이 목적이므로 같은 값의 알파벳 순서는 중요하지 않습니다.

 

alpha[25] = 10000

alpha[24] = 1010

alpha[23] = 100

alpha[22] = 100

alpha[21] = 10

alpha[20] = 1

alpha[19] = 1

 

그리고 최대 값인 9부터 곱하며 내려갑니다.

10000 * 9 + 1010 * 8 + 100 * 7 + 100 * 6 + 10 * 5 + 1 * 4 + 1 * 3

= 90,000 + 8,080 + 700 + 600 + 5 + 4 + 3

= 99,437

 

코드는 다음과 같습니다.

package greedy;

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

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

    int num = Integer.parseInt(br.readLine().trim());
    String[] lines = new String[num];
    int[] alpha = new int[26];

    for (int i = 0; i < num; i++) {
      lines[i] = br.readLine().trim();
    }

    for (int i = 0; i < num; i++) {
      int temp = (int) Math.pow(10, lines[i].length() - 1);
      for (int j = 0; j < lines[i].length(); j++) {
        alpha[(int) lines[i].charAt(j) - 65] += temp;
        temp /= 10;
      }
    }

    Arrays.sort(alpha);
    int index = 9;
    int sum = 0;

    for (int i = alpha.length - 1; i >= 0; i--) {
      if (alpha[i] == 0) {
        break;
      }
      sum += alpha[i] * index;
      index--;
    }

    bw.write(String.valueOf(sum));
    bw.flush();

    br.close();
    bw.close();
  }
}