[분류]
- greedy
[문제링크]
[요구사항]
- 코드의 인덴트를 올바르게 고치는 편집 회수의 최소값을 구한다.
[풀이]
- 각 알파벳의 기여도를 구하는 것이 문제의 핵심이다.
- 1의자리,10의자리,100의자리… 순서로 알파벳이 있으니까 우선 알파벳마다 10의 제곱승을 곱하는 방식으로 기여도를 모두 구한다.
- 이후에 기여도를 기준으로 내림차순 소팅을 하고, 앞에서부터 차례로 9부터 숫자를 부여한다. 이 때, 0이 되도 되는 것들은 가장 뒤에 있으니까 그것을 0으로 준다.
- 이후 모든 수를 더해서 답을 도출한다.
[코드]
//BOJ_1132_합
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Info arr[] = new Info[10];
for(int i=0;i<10;i++){
arr[i] = new Info(i, 0);
}
boolean check[] = new boolean[10];
for(int i=0;i<n;i++){
char[] chars = br.readLine().toCharArray();
long mult = 1;
for(int j=chars.length-1;j>=0;j--){
int index = chars[j]-'A';
arr[index].power+=mult;
mult*=10;
if(j==0) check[index] = true; //0이 들어갈 수 없는 맨 앞에 오는 알파벳 체크
}
}
Arrays.sort(arr, new Comparator<Info>() {
@Override
public int compare(Info o1, Info o2) {
if(o1.power>o2.power) return -1;
else if(o1.power<o2.power) return 1;
else return 0;
}
});
//영향력이 큰 알파벳부터 내림차순으로 소팅
int[] multNums = new int[10];
Arrays.fill(multNums, -1);
for(int i=9;i>=0;i--){
if(!check[arr[i].idx]){
multNums[i] = 0;
break;
}
}
int num = 9;
for(int i=0;i<10;i++){
if(multNums[i]==-1) multNums[i]=num--;
}//앞에서부터 알파벳에 해당하는 숫자를 부여한다. 이때 없는 알파벳도 다 부여해줘도 상관없다. 어짜피 안쓰니까
long res=0;
for(int i=0;i<10;i++){
res+=arr[i].power*multNums[i];
}//어짜피 없는 알파벳은 power가 0이라서 굳이 따로 고려안해주어도 상관없다.
System.out.println(res);
}
public static class Info{
int idx;
long power;
public Info(int idx, long power){
this.idx = idx;
this.power = power;
}
}
}
[통과여부]
[느낀점]
너무 어렵다. 어떻게 이런 발상을 할 수 있는지 모르겠다ㅋㅋ 그리고 맨 앞이 0이 안되게 하려고 추가적인 검증코드를 짜는 것이 생각보다 잘 안되서 너무 오래걸리고 힘들었다.