[백준 1132] 합 - JAVA

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

 

기본 아이디어

1. 알파벳별로 자릿수 가중치를 기록한다. (dp로 기록했는데, 하나의 변수만 써도 충분할 것 같다.)

2. 가중치가 높은 순서대로 9, 8, ... 1을 곱해서 정답에 더한다. (그리디)

 

 

0으로 시작하는 수는 없다.

 

이 조건을 "입력에 0으로 시작하는 수는 주어지지 않는다."로 잘못 해석했다.

문제의 의도는 "0으로 시작하는 수는 사용하면 안된다." 이다. (예제랑 입력 조건으로 유추가능)

 

기댓값이 높은 것부터 탐색하면, 0만 남았을 때 0을 쓸 수 없으면(앞자리가 0인 수가 존재하게 되면) 답이 아니게 된다.

 

따라서, 기댓값이 낮은 것부터 탐색하는게 낫다.

 

나는 조건을 잘못봐서 전처리로 0체크만 따로 추가했다. (그래서 스파게티 코드임)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

class Main {

  // 기댓값이 가장 낮으면서 앞자리가 0이 아닌 알파벳 탐색
  static void initZeroAlpha(int LEN, boolean[] vst, int[][] dp, boolean[] firstAlpha) {
    long min = Long.MAX_VALUE;
    int a = -1;

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

      if (firstAlpha[i]) {
        continue;
      }

      long dep = 1;
      long val = 0; // 기댓값
      for (int j = 0; j < LEN; j++) {
        val += dp[i][j] * dep;
        dep *= 10;
      }

      // 기댓값이 제일 낮은 알파벳 갱신
      if (val < min) {
        a = i;
        min = val;
      }
    }

    vst[a] = true;
  }


  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int NUM = 9;
    int LEN = -1;
    int ALPHA = -1;
    long ans = 0;

    Set<Character> usedAlpha = new HashSet<>();
    boolean[] firstAlpha = new boolean[10];
    boolean[] vst = new boolean[10];
    int[][] dp = new int[10][50];

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

      String s = br.readLine();
      // 앞자리에 사용된 알파벳 체크
      firstAlpha[s.charAt(0) - 'A'] = true;

      // 입력을 첫 자리부터 세기 위해 뒤집음
      s = new StringBuilder(s).reverse().toString();

      // 가장 긴 문자열 길이
      LEN = Math.max(LEN, s.length());

      // dp[0~9][0~LEN] -> i번째 알파벳의 j번째 자리 값이 나온 개수
      for (int j = 0; j < s.length(); j++) {
        char alpha = s.charAt(j);
        dp[alpha - 'A'][j]++;

        usedAlpha.add(alpha);
      }
    }

    ALPHA = usedAlpha.size();

    // 0을 꼭 써야한다면 전처리
    if (ALPHA == 10) {
      initZeroAlpha(LEN, vst, dp, firstAlpha);
      ALPHA--;
    }

    // 알파벳이 더 존재하지 않을 때 까지 반복
    while (ALPHA-- > 0) {
      long max = 0;
      int a = -1;

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

        // 이미 사용한 알파벳이면 패스
        if (vst[i]) {
          continue;
        }

        // i번째 알파벳의 기댓값 계산
        long dep = 1; // 자릿수 가중치
        long val = 0; // 기댓값
        for (int j = 0; j < LEN; j++) {
          val += dp[i][j] * dep;
          dep *= 10;
        }

        // 기댓값이 제일 높은 알파벳 갱신
        if (val > max) {
          a = i;
          max = val;
        }
      }

      ans += NUM * max;
      vst[a] = true;
      NUM--;
    }

    System.out.println(ans);
  }
}