[백준] 1339 단어 수학 (https://www.acmicpc.net/problem/1339)
문제
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.
단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.
N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.
나의 답안
우선 입력받은 단어들을 하나씩 String[] (크기 N) 배열에 담고,
for문을 이용해 하나씩 불러와 단어의 글자수가 가장 긴 것을 찾고
가장 긴 단어의 맨 앞글자에 9를 넣는 방식을 생각해보았으나,
글자 수 가장 큰 단어를 찾은 후 긴 순서대로 재정렬하고,
앞글자부터 9, 8 ,7 을 집어넣을 경우
반복문이 너무 복잡해져 작성해보다가 실패했다.
이후 한참을 생각해봐도 코드 구성이 생각나지 않아 다른 분들의 훌륭한 답안들을 참고했다...
모범 답안
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//n값 및 단어 입력받기
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String [] arr = new String[n];
int [] alpha = new int[26];
for(int i=0; i<n; i++){
arr[i] = sc.next();
}
//알파벳 빈도수 및 글자수에 따른 가중치 부여
for(int i=0; i<n; i++){
int temp = (int)Math.pow(10,arr[i].length()-1);
for(int j=0; j<arr[i].length(); j++){
alpha[(int)arr[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--;
}
System.out.println(sum);
}
}
- n값 및 단어 입력 받기
- Scanner를 사용하여 단어의 수(n)와 단어의 문자열을 입력 받고, arr 배열에 넣음
- 각 단어에서 포함된 알파벳들의 빈도를 체크하기 위한 alpha배열 선언 (26은 알파벳 개수!) - 알파벳 빈도수 및 글자수에 따른 가중치 부여
- 각 문자열의 가중치를 계산하여 알파벳 빈도수 배열 alpha에 누적
- 각 문자열을 순회하면서 문자에 따른 가중치를 계산하고, alpha 배열의 해당 인덱스에 가중치를 더함
예) ABCD > A가 포함된 위치(alpha[0])에 10의 3승, 즉 1000을 더함. B:100, C:10, D:1 더해짐 - 정렬 및 단어 빈도수 별 가중 결과값 합산
- alpha 배열을 내림차순으로 정렬 : 가장 빈도와 가중치가 낮은 알파벳부터 순서대로 정렬
- 가장 큰 수부터 9부터 0까지의 숫자를 곱하여 최종 결과값(총합)을 계산
알파벳 배열을 별도로 선언하여자리수가 높은 수에 10의 지수를 이용하여 가중치를 주고, 여러번 나온 알파벳에 경우에는 그에 맞는 가중 점수를 부여하여 최대값을 구한다는 점이 매우 인상깊었다.