[백준] 1339번 단어수학 문제 순열 활용풀이
1. 문제
1) 링크
2) 문제
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.
단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.
N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.
3) 입력
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.
4) 출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.
더 자세한 문제의 제한사항을 보기 위해서는 위의 링크를 클릭해보자.
2. 풀이
이 문제는 순열을 활용하여 해결할 수 있다. 그리고 0~9까지의 숫자를 사용할 수 있지만 사실 알파벳의 개수가 10개가 아니라면 10개를 다 사용할 필요가 없다. 그리고 최댓값을 구하는 것이기 때문에 만약 알파벳의 개수가 3개라면 사실상 9,8,7을 사용하면 된다.
따라서 이 문제는 d 라는 배열을 사용해서 이를 순열로 만들면서 조합을 바꾸어나갈 것이다.
ArrayList<Character> cha=new ArrayList<>(); //문제에서 입력받은 알파벳
for(int i=0; i<n; i++){
inp[i]=sc.next();
for(char ch: inp[i].toCharArray()){
if (!cha.contains(ch)){
cha.add(ch);
}
}
}
int len=cha.size();
d=new int[len];
for(int i=0; i<len; i++){
d[i]=9-i; //숫자들을 저장
}위의 코드처럼 문제에서 알파벳을 중복하지 않고 받은 뒤에 그 크기만큼 필요한 숫자를 저장한다. 위에서도 언급했지만 최댓값이기 때문에 9부터 하나씩 감소시켜주면서 저장하면 된다.
그 뒤에 d라는 배열을 Arrays.sort(d) 를 활용해서 오름차순으로 정렬한다. 이유는 순열을 사용할 때 점차 숫자를 키워나가면서 순열의 다음 숫자를 구할 것이기 때문이다.
순열은 저번 포스팅에서도 다루었듯이,
public static boolean next_permutation(int[] d){
int i=d.length-1;
while(i>0 && d[i-1]>=d[i]){
i--;
}
if (i<=0) return false;
int j=d.length-1;
while(d[i-1]>=d[j]){
j--;
}
int tmp=d[i-1];
d[i-1]=d[j];
d[j]=tmp;
j=d.length-1;
while(i<j){
tmp=d[i];
d[i]=d[j];
d[j]=tmp;
i++;
j--;
}
return true;
}위와 같은 코드처럼 구할 수 있다.
다음으로 corr[] 라는 배열을 하나 준비시켜 준다. 이는 알파벳과 숫자를 연결해주는 배열이라고 할 수 있다. 다 대문자만 들어오기 때문에 index의 값은 알파벳 - 'A' 를 기준으로 생각했고 그렇게 되면 A~Z까지 모두 자신의 값이 존재한다. 즉 다시 말해서 corr[cha.get(i)-'A']= d[i] 이런식으로 코드를 준비하는 것이다. 그렇다면 만약 알파벳이 B라면 corr[1]의 값이 호출되는 것이라고 할 수 있다. 아스키코드를 기준으로 영어 대문자 중 'A'가 가장 작은 값이기 때문에 'A'를 뺀 값으로 index를 설정해주었다.
이후의 코드는 정말로 하나하나 숫자를 입력받아서 해당 합을 구해보고 최대값이면 값을 지속적으로 업데이트해주면 된다.
import java.util.*;
public class Main{
public static boolean next_permutation(int[] d){
int i=d.length-1;
while(i>0 && d[i-1]>=d[i]){
i--;
}
if (i<=0) return false;
int j=d.length-1;
while(d[i-1]>=d[j]){
j--;
}
int tmp=d[i-1];
d[i-1]=d[j];
d[j]=tmp;
j=d.length-1;
while(i<j){
tmp=d[i];
d[i]=d[j];
d[j]=tmp;
i++;
j--;
}
return true;
}
static int[] d;
static int[] corr=new int[30]; //알파벳과 숫자를 대응시키는 것
public static int summing(String[] inp, ArrayList<Character> cha){
int sum=0;
int len=inp.length;
for(int i=0; i<cha.size(); i++){
corr[cha.get(i)-'A']=d[i];
}
for(int i=0; i<len; i++){
int ttmp=0;
for(char ch: inp[i].toCharArray()){
ttmp=ttmp*10+ corr[ch-'A'];
}
sum+=ttmp;
}
return sum;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
String[] inp=new String[n];
ArrayList<Character> cha=new ArrayList<>(); //문제에서 입력받은 알파벳
for(int i=0; i<n; i++){
inp[i]=sc.next();
for(char ch: inp[i].toCharArray()){
if (!cha.contains(ch)){
cha.add(ch);
}
}
}
int len=cha.size();
d=new int[len];
for(int i=0; i<len; i++){
d[i]=9-i; //숫자들을 저장
}
Arrays.sort(d); //낮은것부터 높은 것 순서대로 가기 위해서
int ans=0;
do{
int temp=summing(inp, cha);
if (temp>ans){
ans=temp;
}
}while(next_permutation(d));
System.out.println(ans);
}
}