[Baekjoon Online Judge] 1339번: 단어 수학 - 풀이 추가 예정

1339번: 단어 수학

1339번: 단어 수학

 HashMap을 활용하여 풀이하였다. map의 key 값으로 알파벳을 넣었고, value는 해당 key 값의 자릿수 가중치이다. 예를 들면, 입력이

 

2

GCF

ACDEB 

 

 라고 가정하자. 그렇게 되면 GCF, ACDEB는 각각 key 값으로 들어가게되고, GCF에서 G는 100의 자리 이기 때문에 value로 100이란 값을 가지게 된다. C는 10, F는 1이된다. ACDEB를 보면 A는 10000, C는 1000, D는 100, E는 10, B는 1이된다.

 

 각 자리의 가중치를 합하면 결과적으로

 

key	value
A	10000
B	1
C	1010
D	100
E	10
F	1
G	100

 이러한 map을 형성하게 된다. 이제 0 부터 9 까지 숫자를 바꿔서 가장 큰 수를 도출하면 되는데, keySetList를 만들어 각 value가 큰 순서로 list를 정렬하였다. 그 후 각 자리수 가중치에 실제 곱한 가중치 값을 만들어 합하게 되면 원하는 최대 값이 나오게 된다.

 

A 10000 x 9 = 90000

C 1010 x 8 = 8080

D 100 x 7 = 700

G 100 x 6 = 600

E 10 x 5 = 50

B 1 x 4 = 4

F 1 x 3 = 3

 

 전부 더하면 99437이 나오게 된다.

 

import java.io.*;
import java.util.*;

public class Baekjoon1399 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        Map<String, Integer> alphabetMap = new HashMap<>(); // 각 단어당 가중치 값을 저장하는 map
        int n = Integer.parseInt(bufferedReader.readLine()); // 단어의 개수

        for (int i = 0; i < n; i++) {
            String string = bufferedReader.readLine(); // 단어 저장
            int length = string.length() - 1; // 각 단어 자리수

            for (int j = 0; j <= length; j++) {
                String alphabet = String.valueOf(string.charAt(j)); // 해당 자리수의 알파벳
                if (alphabetMap.containsKey(alphabet)) { // map 에 알파벳이 있다면
                    // 기존 값에 더해줌
                    alphabetMap.put(alphabet, alphabetMap.get(alphabet) + (int) Math.pow(10, length - j));
                } else { // map 에 알파벳이 없다면
                    // 새로운 값을 추가
                    alphabetMap.put(alphabet, (int) Math.pow(10, length - j));
                }
            }
        }

        List<String> keySetList = new ArrayList<>(alphabetMap.keySet()); // map 에 저장된 알파벳 집합 list
        Collections.sort(keySetList, (x, y) -> { // map 의 value 가 큰 순서로 list 의 key 값으로 정렬
            return alphabetMap.get(y).compareTo(alphabetMap.get(x));
        });

        int result = 0; // 결과값 저장하는 변수
        int weight = 9; // 9 ~ 0 까지의 가중치
        for (int i = 0; i < keySetList.size(); i++) {
            result += alphabetMap.get(keySetList.get(i)) * weight; // 큰 자리수 부터 가중치를 하나씩 내려가며 곱하고 더해줌
            --weight;
        }

        bufferedWriter.write(String.valueOf(result));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

 어느 부분에서 greedy를 활용한 부분인지 확실하게 모르겠다. 여러 코드를 비교해 보며 다른 풀이 과정도 추가해 나갈 예정이다.