[백준 1339] 단어 수학

https://www.acmicpc.net/problem/1339

 

그리디 알고리즘 문제이다.

# 풀이방법
1. 알파벳 배열을 만들고, 자릿수에 따라 가중치를 부여한다. (e.g. ABC라면 각 가중치는 A 100, B 10, C 1)
2. 가중치가 가장 높은 알파벳에 9, 그 다음에 8, ... 과 같이 숫자를 배정한다.

 

내 풀이 (어렵게 풀었음)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

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());

        String[] words = new String[N];
        for (int i = 0; i < N; i++) {
            words[i] = br.readLine();
        }

        // 가중치 배열
        int[][] weight = new int[26][3];

        // - 0열 : 알파벳 저장 ('A'는 0, 'Z'는 25)
        for (int i = 0; i < 26; i++) {
            weight[i][0] = i;
        }

        // - 1열 : 가중치 저장
        for (int i = 0; i < N; i++) {
            String str = words[i];
            int digit = str.length() - 1;
            for (int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                weight[c - 'A'][1] += Math.pow(10, digit--);
            }
        }

        // 가중치를 기준으로 내림차순 정렬
        Arrays.sort(weight, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });

        // - 2열 : 알파벳에 배정할 숫자 저장
        int num = 9;
        for (int i = 0; i < 26; i++) {
            if (weight[i][1] == 0)  break;  // 가중치가 0이라면 사용되지 않은 알파벳이므로 종료
            weight[i][2] = num--;
        }

//        // 결과 출력 (디버깅용)
//        for (int i = 0; i < 26; i++) {
//            if (weight[i][1] > 0) { // 가중치가 0보다 큰 항목만 출력
//                System.out.println((char)(weight[i][0] + 'A') + ": 가중치=" + weight[i][1] + " / 배정 숫자=" + weight[i][2]);
//            }
//        }

        // 결과 계산
        int res = 0;
        for (int i = 0; i < 26; i++) {
            res += weight[i][1] * weight[i][2];
        }
        System.out.println(res);
    }
}

 

다른 사람 풀이

가중치에 따라 숫자만 배정해주면 되고 어떤 알파벳인지는 관계 없으므로, 굳이 힘들게 2차원 배열을 쓰지 않아도 된다.😅

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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());

        String[] words = new String[N];
        for (int i = 0; i < N; i++) {
            words[i] = br.readLine();
        }

        // 알파벳 배열 ('A'는 0, 'Z'는 25)
        int[] alphabet = new int[26];

        // 가중치 저장
        for (int i = 0; i < N; i++) {
            String str = words[i];
            int digit = str.length() - 1;
            for (int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                alphabet[c - 'A'] += Math.pow(10, digit--);
            }
        }

        // 가중치 기준 정렬
        Arrays.sort(alphabet);

        // 결과 계산
        int res = 0;
        int num = 9;
        for (int i = 25; i >= 0; i--) {
            if (alphabet[i] == 0)  break;
            res += alphabet[i] * num--;
        }
        System.out.println(res);
    }
}

 

1. 문제 요약

이 문제는 주어진 단어들의 합을 최대화하기 위해 각 알파벳에 0부터 9까지의 숫자를 할당하는 문제입니다. 각 알파벳은 서로 다른 숫자로 바꿔야 하며, 동일한 알파벳은 같은 숫자로 바꿔야 합니다. 목표는 단어들의 합을 최대화하는 것입니다.

 

2. 핵심 아이디어

1. 가중치 계산:
   • 각 알파벳이 수의 어느 자리에 위치하는지에 따라 가중치를 부여합니다. 예를 들어, 'ABC'라는 단어에서 'A'는 백의 자리, 'B'는 십의 자리, 'C'는 일의 자리에 해당하므로 각각 100, 10, 1의 가중치를 가집니다.
   • 이를 위해 각 단어를 읽으면서, 각 알파벳의 자릿수에 해당하는 가중치를 계산하여 alphabet 배열에 저장합니다.
2. 가중치 정렬:
   • 가중치를 기준으로 내림차순 정렬하여, 가중치가 높은 알파벳이 더 높은 숫자를 배정받을 수 있도록 합니다.
   • Java의 Arrays.sort 메서드를 사용하여 alphabet 배열을 오름차순으로 정렬한 후, 역순으로 접근하여 가중치가 높은 알파벳부터 숫자를 배정합니다.
3. 숫자 배정 및 결과 계산:
   • 가중치가 높은 알파벳부터 차례대로 9, 8, ..., 0의 숫자를 배정합니다. 이를 통해 전체 합이 최대가 되도록 합니다.
   • 각 알파벳에 배정된 숫자와 가중치를 곱하여 최종 결과를 계산합니다.

 

3. 참고 - "2차원 배열 내림차순 정렬" 코드 해석

Arrays.sort(weight, new Comparator<int[]>() { 
    @Override 
    public int compare(int[] o1, int[] o2) { 
    	return o2[1] - o1[1]; 
    } 
});

1. Arrays.sort(weight, ...):
   • Arrays.sort 메서드는 배열을 정렬하는 데 사용됩니다.
   • weight 배열은 정렬 대상입니다.
   • 두 번째 인수로 Comparator<int[]>를 사용하여 배열의 각 요소의 비교방식을 정의합니다.
2. Comparator<int[]>:
   • Comparator 인터페이스는 비교 로직을 정의하는 데 사용됩니다.
   • int[]는 배열의 각 요소 타입입니다. 여기서는 int[] 타입의 배열을 비교합니다.
3. compare 메서드:
   • Comparator 인터페이스의 compare 메서드를 구현하여 두 배열을 비교하는 방법을 정의합니다.
   • int[] o1과 int[] o2는 비교할 두 배열입니다.
   • o2[1] - o1[1]는 두 배열의 1번째 인덱스(즉, 가중치)를 비교하여 내림차순으로 정렬하도록 합니다.
   • 비교 결과가 양수이면 o2가 o1보다 크다는 의미입니다. 이는 o2가 앞에 오도록 하여 내림차순 정렬을 합니다. (return 값이 양수면 자리 바꿈)