[백준 | Java] 1339 단어 수학

내 풀이

오답 풀이

각 단계마다 최선의 선택을 하는 그리디 알고리즘을 사용했다.
풀이과정은 다음과 같다.

1. 각 N[i]를 돌며 N[i]을 key, 각 N[i]의 length-1을 value로 저장
   👉 같은 key에는 value 중 최댓값으로 저장
   • G = 3, C = 2, F = 1
   • A = 5, C = 4, D = 3, E = 2, B = 1
     👉 C = 4로 저장
2. 각 value에 저장된 숫자 내림차순으로 정리
   • A, C, G, D, E, F, B
   • 5, 4, 3, 3, 2, 1, 1
3. 내림차순 정리된 hashmap의 value에 9부터 0 방향으로 하나씩 대입
   • A, C, G, D, E, F, B
   • 9, 8, 7, 6, 5, 4, 3
4. 알파벳에 대입해서 계산

위의 풀이과정으로 풀었더니 오답이 됐다. 나와있는 모든 테스트 케이스는 다 정답인데 시간초과도 아닌거같고, 아직 오답의 원인은 못 찾았지만 아무래도 내가 못 찾은 반례가 있어 바로 오답 처리가 되는 거 같다. 틀린 원인은 계속 찾아봐야겠다.

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

public class Main {
    static int N;
    static String[] str;
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        str = new String[N];
        for (int i = 0; i < N; i++) {
            str[i] = br.readLine();
        }
        result = 0;
        max();
        System.out.println(result);
    }
    static void max() {
        Map<String, Integer> map = new HashMap<>();
        // 1
        for (int i = 0; i < N; i++) {
            String[] tmp = str[i].split("");
            for (int j = 0; j < str[i].length(); j++) {
                if (map.containsKey(tmp[j])) {
                    if (str[i].length()-j > map.get(tmp[j])) {
                        map.put(tmp[j], str[i].length()-j);
                    }
                } else {
                    map.put(tmp[j], str[i].length()-j);
                }
            }
        }

		// 2
        List<String> keys = new ArrayList<>(map.keySet());
        Collections.sort(keys, (v1, v2) -> (map.get(v2).compareTo(map.get(v1))));

        for (int i = 0; i < keys.size(); i++) {
            map.put(keys.get(i), 9-i);
        }

        for (int i = 0; i < N; i++) {
            String[] tmp = str[i].split("");
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < str[i].length(); j++) {
                sb.append(map.get(tmp[j]));
            }
            result += Integer.parseInt(sb.toString());
        }
    }
}

정답 풀이

풀이는 내가 풀었던 풀이와 비슷하지만 같은 알파벳 저장 시 최댓값 연산을 따로 안하고 배열에 바로 저장되는 것과, 알파벳의 자릿수만큼 10을 곱한 값에 최종적으로 9부터 곱한 값을 더하여 답을 도출하는 부분이 달랐다.

👉 자세한 풀이는 다음과 코드 내 주석을 참고

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

public class Main {
    static int N;
    static String[] str;
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        str = new String[N];
        for (int i = 0; i < N; i++) {
            str[i] = br.readLine();
        }
        result = 0;
        max();
        System.out.println(result);
    }
    static void max() {
        int[] alpha = new int[26];  // 0부터 25까지 (각 알파벳의 순서-1)에 맞게 저장됨
        for (int i = 0; i < N; i++) {  // i = 0
            int tmp = (int)Math.pow(10, str[i].length()-1);  // 10 * 10 = 100
            for (int j = 0; j < str[i].length(); j++) {
                alpha[(int)str[i].charAt(j) - 65] += tmp;  // G = 71, 71-65 = 6(G는 7번째 알파벳) => alpha[6] = 100 저장
                tmp /= 10;  // 다음 알파벳부터 자릿수가 하나씩 줄어들며 저장
            }
        }

        Arrays.sort(alpha);
        int idx = 9;
        for (int i = alpha.length-1; i >= 0; i--) {
            if (alpha[i] == 0)
                break;
            result += alpha[i] * idx;
            idx--;
        }
    }
}