📌 출처
📝 문제
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.
단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.
N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.
⌨ 입력
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.
🖨 출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.
💻 내 코드
1. 리스트를 사용하여 구현
package com.ll.백준.BFS_DFS.p1339;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
List<String> words = new ArrayList<>();
int[] alphabetCount = new int[26];
for(int i = 0; i < N; i++) {
String word = br.readLine();
words.add(word);
int size = word.length();
for(int j = 0; j < size; j++) {
alphabetCount[word.charAt(j) - 'A'] += Math.pow(10, size - j - 1);
}
}
Arrays.sort(alphabetCount);
int index = 9;
int sum = 0;
for(int i = 25; i >= 0; i--) {
if(index == 0) {
break;
}
sum += alphabetCount[i] * index;
index--;
}
System.out.println(sum);
}
}
✏ 설명
처음에는 두 개의 숫자를 비교해서 구하는 문제인 줄 알고 두 숫자 중 자릿수가 가장 큰 것부터 9 8 7..이런 식으로 숫자를 부여했다.
그런데 알고보니 2개의 숫자가 아니라 N개의 숫자였다...
이걸 하나하나 다 비교를 할 수도 없고 참..
한참을 고민하다가 결국 푸는 방법을 찾아보았다.
그 결과 푸는 방법은 다음과 같다.
- 문제에서 주어진 예시처럼 아래 두 문자열이 주어진다고 가정해보자.
- GCF
- ACDEB
- 이 문제의 정답은 max 값을 찾는 것이다.
- 따라서 높은 자릿수에 높은 값(9 ~ 0)을 부여하면 된다.
- 여기까지는 내가 생각한 것과 같다.
- GCF는 총 3자리이다. 따라서 100부터 시작한다.
- 100G, 10C, 1F
- ACDEB는 총 5자리이다. 따라서 10000부터 시작한다.
- 10000A, 1000C, 100D, 10E, 1B
- GCF의 값과 ACDEB의 값을 더해보자.
- 10000A, 1B, 1010C, 100D, 10E, 1F, 100G 가 나오게 된다.
- 이렇게 나온 값을 26개(A~Z의 개수)의 int형 배열을 생성하여 넣어주고, 정렬한다.
- 높은 값부터 9~0을 곱하고 더해주면 답을 구할 수 있다.
- 직접 보여주면 다음과 같다.
- [10000, 1, 1010, 100, 10, 1, 100, 0, 0, ......]
- 위 배열을 정렬한다.
- [0, 0, ... , 0, 1, 1, 10, 100, 100, 1010, 10000]
- 높은 값부터 9~0을 곱하고 더해준다.
- 10000 X 9 + 1010 X 8 + 100 X 7 + 100 X 6 + 10 X 5 + 1 X 4 + 1 X 3 = 99437
- 이 값은 10000A + 1010C + 100D + 100G + 10E + 1B + 1F 에서 A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7를 대입한 결과와 같다.
어떻게 이런 방법을 생각하게 되는 것일까
뭐니뭐니해도 문제를 많이 풀어보는 것이 답이지 싶다..
열심히 풀어봐야겠다.
