IT Docs

문제 링크 : https://www.acmicpc.net/problem/1339
문제 등급 : Gold IV

입력

2
GCF
ACDEB

문제 해결 로직

1. 알파벳이 들어갈 배열 생성
2. 각 문자열의 알파벳을 문자형으로 받고 배열의 해당 문자의 위치에 자릿수를 삽입한다.
   1. A의 경우 'A'를 뺄셈 하여 0번을 받는다.
   2. A의 위치의 값이 0이 아니면 A의 값과 더해주고 값이 0이라면 A에 값을 삽입한다.
   3. 위와 같이 자릿수를 구하면 A = 10000, C = 1000, D = 100, E = 10, B = 1, G = 100, C = 10, F = 1과 같이 자릿수를 구할수 있다.
   4. C의 경우 앞에서 1000 넣어 최종적으로 C = 1010이 된다.
3. 자리수를 구한 배열을 내림 차순으로 정렬한다.
4. 정렬된 배열에서 가장 큰 값인 9부터 0까지 배열의 요소와 곱한다.
5. 반복문을 돌면서 최대 값을 구한다.

이 문제를 분석했을 때 전체 탐색으로 풀려고 하였다. 하지만 전체 탐색으로 푸는 법도 막막하여 풀이를 찾아보았다.

전체 탐색하면 시간 초과가 발생하여 전체 탐색을 하지 않고 자릿수를 구해 최댓값을 구하는 풀이를 보았다.

이 문제는 아주 그리디스러운 문제라는 걸 느꼈다.

아래와 같이 소스를 공유합니다.

public class 단어 수학 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] ap = new int[26];

        for(int i = 0; i < n; i++) {
            char[] str = sc.next().toCharArray();

            for (int j = 0; j < str.length; j++) {
                int pow = (int) Math.pow(10, str.length - j - 1);
                char c = str[j];
                int s = str[j] - 'A';
                if(ap[s] != 0){
                    ap[s] += pow;
                }else {
                    ap[s] = pow;
                }
            }
        }

        int sum = 0;
        
        // 0 제거 후 내림차순으로 정렬
        List<Integer> list = Arrays.stream(ap).boxed().filter((item) -> item != 0).sorted(Collections.reverseOrder()).collect(Collectors.toList());

        for(int i = 0; i < list.size(); i++) {
            sum += list.get(i) * (9 - i);
        }

        System.out.println(sum);
    }
}