[BOJ] 1132 - 합 (Java)

접근법

각 알파벳이 어떤 수를 나타내야 가장 큰 수가 나오게 되는지를 확인하는 문제

충분히 그리디 알고리즘으로도 해결이 되는 문제.

각 알파벳마다 나오는 자릿수만큼을 모조리 더하면 가장 큰 수가 될 수 있는 경우들이 보이게 된다.

합이 높은 수에 높은 수를 배치하게 되면 가장 큰 수가 나올 수 있을 것이다.

문제는 제일 처음 0은 올 수 없다는 점으로 이 부분만 잘 처리해 주면 문제 해결은 어렵지 않다.

---

코드

package boj;

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

public class BOJ_1132_합 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		long[] alpha_cnt = new long[10];
		for (int i = 0; i < 10; i++) {
			alpha_cnt[i] = 0;
		}
		boolean[] can_zero_arr = new boolean[10];
		for (int i = 0; i < 10; i++) {
			can_zero_arr[i] = true;
		}
		for (int i = 0; i < N; i++) {
			String alphaNum = br.readLine();
			for (int j = alphaNum.length() - 1; j >= 0; j--) {// 뒤에서부터 확인
				alpha_cnt[(int) alphaNum.charAt(j) - 65] += (long) Math.pow(10, (alphaNum.length() - 1) - j);
			}
			can_zero_arr[alphaNum.charAt(0) - 65] = false; // 얘는 처음은 안돼

		}
		int alphabet_cnt = 0;
		for (int i = 0; i < 10; i++) {
			if (alpha_cnt[i] > 0)
				alphabet_cnt++;
		}

		if (alphabet_cnt == 10) { // 0이 있어야해
			long min_val = Long.MAX_VALUE;
			int min_index = -1;
			for (int i = 0; i < 10; i++) {
				if (can_zero_arr[i] && min_val > alpha_cnt[i]) { // 0이 될 수 있음
					min_val = alpha_cnt[i];
					min_index = i;
				}
			}

			alpha_cnt[min_index] = 0; // 어차피 곱해봐야 0임

		}

		long sum = 0;
		Arrays.sort(alpha_cnt);
		for (int i = 9; i >= 0; i--) {
			sum += i * alpha_cnt[i];
		}
		System.out.println(sum);

	}
}

결과

메모리 시간 언어

14268KB

124ms

Java