[백준 / Java] 1339: 단어 수학 (그리디)

난이도: Gold 4

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

 

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 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 복사

2
AAA
AAA

예제 출력 1 복사

1998

예제 입력 2 복사

2
GCF
ACDEB

예제 출력 2 복사

99437

예제 입력 3 복사

10
A
B
C
D
E
F
G
H
I
J

예제 출력 3 복사

45

예제 입력 4 복사

2
AB
BA

예제 출력 4 복사

187

---

 

일단 변수를 다음과 같이 선언한다.

weight는 각 알파벳 별 가중치를 저장한 맵이다.

이 가중치는 알파벳의 자릿수가 높거나, 알파벳이 자주 나올수록 커진다.

 

    int N = Integer.parseInt(br.readLine());    // 단어의 개수

    String[] words = new String[N];             // 1차원 단어 배열

    Map<Character, Integer> weight = new HashMap<>();   // 가중치 맵

 

 

단어를 입력받고 각 단어를 구성하는 알파벳의 가중치를 세팅한다.

자세한 설명은 주석에 적혀있다.

 

    // N개의 단어 입력받기

    for (int i = 0; i < N; i++) {

        words[i] = br.readLine();           // i번째 단어 입력받기

        int length = words[i].length();     // i번째 단어의 길이

       

        // i번째 단어를 구성하는 각 알파벳의 가중치 세팅

        for (int j = 0; j < length; j++) {

            char ch = words[i].charAt(j);   // i번째 단어의 j번째 알파벳

            // 해당 알파벳의 가중치 세팅 => 알파벳이 앞에 있고, 자주 나올수록 가중치가 높아짐

            // 만약 length가 4라면 다음과 같음

            // j = 0: (int)Math.pow(10, length - 0 - 1) = 10^3 = 1000

            // j = 1: (int)Math.pow(10, length - 1 - 1) = 10^2 = 100

            // j = 2: (int)Math.pow(10, length - 2 - 1) = 10^1 = 10

            // j = 3: (int)Math.pow(10, length - 3 - 1) = 10^0 = 1

            // 인덱스가 앞에 있을수록 높은 자릿수이기 때문에 가중치가 높아짐

            // 그리고 앞에서 저장했던 가중치의 값에서 이 값을 더하므로 알파벳이 자주 나올수록 가중치가 높아짐

            weight.put(ch, weight.getOrDefault(ch, 0) + (int)Math.pow(10, length - j - 1));

        }

    }

 

 

위에서 가중치 맵을 다 세팅하고, 이 맵의 키(알파벳)에 해당하는 집합(Set)을 List로 바꾼다.

List로 바꾸는 이유는 알파벳의 가중치가 큰 순서대로 내림차순 정렬을 해야 하는데, Set은 순서가 없으므로 정렬을 할 수가 없기 때문이다.

이 코드를 작성하면서 Collection의 sort 메서드도 다시 한번 명확하게 복습을 하게 되었다.

 

    // 가중치 맵의 키(알파벳) 집합을 인자로 받는 알파벳 리스트 생성

    List<Character> alphabets = new ArrayList<>(weight.keySet());

   

    // 알파벳 리스트를 가중치가 큰 순서대로 내림차순 정렬

    alphabets.sort((o1, o2) ->

        weight.get(o2) - weight.get(o1)

    );

 

 

알파벳을 숫자로 매핑하는 맵(alphabetToNum)을 새로 생성한다.

위에서 알파벳 리스트(alphabets)를 가중치가 큰 순서대로 내림차순 정렬했으므로, 알파벳 리스트(alphabets)를 차례대로 탐색하면서 num을 9부터 차례대로 1씩 감소시키면서 알파벳을 숫자로 매핑하는 맵(alphabetToNum)에 추가하면 된다.

이렇게 하면 자릿수가 높고 자주 나오는 알파벳은 자연스럽게 큰 숫자를 가져가게 된다.

 

    Map<Character, Integer> alphabetToNum = new HashMap<>();    // 알파벳을 숫자로 매핑하는 맵

    int num = 9;    // 9부터 차례대로 줄일 예정

   

    // 가중치가 큰 순서대로 정렬된 알파벳 탐색

    for (char alphabet : alphabets) {

        // 가중치가 큰 알파벳일수록(자릿수가 높고, 자주 나올수록) 큰 숫자를 가져감

        alphabetToNum.put(alphabet, num--);

    }

 

 

이제 최종 단계이다.

위에서 알파벳 별로 숫자를 모두 매핑했으므로, 전체 합을 구할 sum 변수에 각 단어의 숫자를 모두 더하고 출력하면 된다.

   

    int sum = 0;    // 전체 단어들의 합의 최댓값 => 위에서 최댓값이 되게 세팅해줬으므로 더하기만 하면 됨

   

    // 단어 탐색

    for (String word : words) {

        int value = 0;  // 각 단어의 숫자

       

        // 각 단어의 알파벳 탐색

        for (char ch : word.toCharArray()) {

            value = value * 10 + alphabetToNum.get(ch); // 단어를 숫자로 바꾸기

        }

       

        sum += value;   // 각 단어의 숫자를 전체 단어들의 합 변수에 누적시키기

    }

   

    System.out.println(sum);    // 전체 단어들의 합의 최댓값 출력

 

 

 

그리디는 구현력이 중요한 것 같다. 심지어 코드를 간단하게 작성할 수 있는 것도 중요한 것 같다.

구현력이 부족한 나로서는 그리드를 정말 내 힘으로만 온전히 풀기가 너무 어렵다.

내 힘으로만 풀었다고 생각했으나 "틀렸습니다"를 보면 참 스트레스를 받게 한다.

결국 풀이 과정은 챗지피티의 힘을 좀 빌렸는데 전체 코드가 생각보다 짧아서 어이가 없게 만든다.

문제 로직은 이해가 되는데 코드 작성을 명확하고 간단하게 못 하니까 답답하다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class P1339_단어수학 {
    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];                // 1차원 단어 배열
        Map<Character, Integer> weight = new HashMap<>();    // 가중치 맵
        
        // N개의 단어 입력받기
        for (int i = 0; i < N; i++) {
            words[i] = br.readLine();            // i번째 단어 입력받기
            int length = words[i].length();        // i번째 단어의 길이
            
            // i번째 단어를 구성하는 각 알파벳의 가중치 세팅
            for (int j = 0; j < length; j++) {
                char ch = words[i].charAt(j);    // i번째 단어의 j번째 알파벳
                // 해당 알파벳의 가중치 세팅 => 알파벳이 앞에 있고, 자주 나올수록 가중치가 높아짐
                // 만약 length가 4라면 다음과 같음
                // j = 0: (int)Math.pow(10, length - 0 - 1) = 10^3 = 1000
                // j = 1: (int)Math.pow(10, length - 1 - 1) = 10^2 = 100
                // j = 2: (int)Math.pow(10, length - 2 - 1) = 10^1 = 10
                // j = 3: (int)Math.pow(10, length - 3 - 1) = 10^0 = 1
                // 인덱스가 앞에 있을수록 높은 자릿수이기 때문에 가중치가 높아짐
                // 그리고 앞에서 저장했던 가중치의 값에서 이 값을 더하므로 알파벳이 자주 나올수록 가중치가 높아짐
                weight.put(ch, weight.getOrDefault(ch, 0) + (int)Math.pow(10, length - j - 1));
            }
        }
        
        // 가중치 맵의 키(알파벳) 집합을 인자로 받는 알파벳 리스트 생성
        List<Character> alphabets = new ArrayList<>(weight.keySet());
        
        // 알파벳 리스트를 가중치가 큰 순서대로 내림차순 정렬
        alphabets.sort((o1, o2) ->
            weight.get(o2) - weight.get(o1)
        );
        
        
        Map<Character, Integer> alphabetToNum = new HashMap<>();    // 알파벳을 숫자로 매핑하는 맵
        int num = 9;    // 9부터 차례대로 줄일 예정
        
        // 가중치가 큰 순서대로 정렬된 알파벳 탐색
        for (char alphabet : alphabets) {
            // 가중치가 큰 알파벳일수록(자릿수가 높고, 자주 나올수록) 큰 숫자를 가져감
            alphabetToNum.put(alphabet, num--);
        }
        
        int sum = 0;    // 전체 단어들의 합의 최댓값 => 위에서 최댓값이 되게 세팅해줬으므로 더하기만 하면 됨
        
        // 단어 탐색
        for (String word : words) {
            int value = 0;    // 각 단어의 숫자
            
            // 각 단어의 알파벳 탐색
            for (char ch : word.toCharArray()) {
                value = value * 10 + alphabetToNum.get(ch);    // 단어를 숫자로 바꾸기
            }
            
            sum += value;    // 각 단어의 숫자를 전체 단어들의 합 변수에 누적시키기
        }
        
        System.out.println(sum);    // 전체 단어들의 합의 최댓값 출력
    }
}