[백준] 1339번. 단어 수학(JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        String[] string = new String[N];

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

        HashMap<Character, Integer> map = new HashMap<>();

        // 대문자 알파벳으로 루프 돌면서 초기화
        for (char ch = 'A'; ch <= 'Z'; ch++) {
            map.put(ch, 0);
        }

        for(String x : string){
            for(int i = 0; i< x.length(); i++){
                int value = map.get(x.charAt(x.length() - i - 1)); // 현재 값 가져오기
                map.put(x.charAt(x.length() - i - 1), value + (int)Math.pow(10, i));
            }
        }

        List<Map.Entry<Character, Integer>> entryList = new ArrayList<>(map.entrySet());

        // List를 값의 크기에 따라 내림차순으로 정렬
        Collections.sort(entryList, (e1, e2) -> e2.getValue().compareTo(e1.getValue()));


        // 정렬된 순서대로 출력
        for (int i = 0; i < 10; i++) {
            entryList.get(i).setValue(9-i);
        }

        int sum = 0;

        for (String str : string) {
            int result = 0;
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                boolean found = false;
                for (Map.Entry<Character, Integer> entry : entryList) {
                    if (entry.getKey() == ch) {
                        found = true;
                        result = result * 10 + entry.getValue();
                        break;
                    }
                }
                if (!found) {
                    // 해당 문자가 맵에 없는 경우에는 그냥 넘어감
                }
            }
            sum += result;
        }

        System.out.println(sum);


    }

}

 

그리디 알고리즘에 대한 문제로 문제 해결 자체에 대한 아이디어를 떠올리는 데에 오랜 시간이 걸리진 않았다. 결국 크기를 결정하는 것은 자릿수가 높은 것일수록 큰 숫자를 배정받아야 한다는 아이디어를 이용했다. 또한, 최대 10번 반복되기 때문에 10의 지수승을 자릿수의 값으로 배정함으로써 자릿수가 높은 것이 더 큰 영향을 미칠 수밖에 없게 했다.

 

다만 초반에 잡아내지 못한 코딩 오류가 있었다. 문자 추출의 인덱스를 제대로 처리하지않아서
10
ABB
BC
BC
BC
BC
BC
BC
BC
BC
BC
의 경우 A에 111이 저장되는 문제가 발생했다. x.charAt에서 put인덱스는 제대로 지정했는데 value값 인덱스를 잘못 설정해서 그런 것이었다. 더욱 인덱스 설정에 주의할 필요가 있어 보인다.

List<Map.Entry<Character, Integer>> entryList = new ArrayList<>(map.entrySet());

리스트에 해쉬맵을 벨류로 저장하는 방법이다. 잘 알아두면 쓸모가 많을 것 같다.

Collections.sort(entryList, (e1, e2) -> e2.getValue().compareTo(e1.getValue()));

값을 비교하여 내림차순 정렬하는 방법이다. 리스트에서 내림차순 정렬을 할 때도 많으므로 이 또한 확실히 알아두어야 할 것 같다.