백준 1260번: 단어 수학

문제 풀이

1. 각 알파벳이 차지하는 자릿수 가중치를 계산
   • 예를 들어, GCF에서 G는 백의 자리(100), C는 십의 자리(10), F는 일의 자리(1)를 가집니다.
   • 이를 모든 단어에 대해 계산하여 알파벳별 중요도를 구합니다.
2. 가중치가 높은 알파벳에 큰 숫자를 할당
   • 가중치가 높은 알파벳부터 9, 8, 7, ... 순으로 숫자를 배정합니다.
3. 실제 숫자로 변환한 후 합을 계산

 

코드 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] words = new String[N];
        for (int i = 0; i < N; i++) {
            words[i] = sc.next();
        }
        sc.close();

        // 1. 각 알파벳별 가중치 계산
        Map<Character, Integer> weightMap = new HashMap<>();
        for (String word : words) {
            int power = (int) Math.pow(10, word.length() - 1);
            for (char ch : word.toCharArray()) {
                weightMap.put(ch, weightMap.getOrDefault(ch, 0) + power);
                power /= 10;
            }
        }
        
        // 2. 가중치가 높은 순서대로 정렬
        List<Map.Entry<Character, Integer>> sortedWeights = new ArrayList<>(weightMap.entrySet());
        sortedWeights.sort((a, b) -> b.getValue().compareTo(a.getValue()));
        
        // 3. 숫자 배정 (9부터 할당)
        Map<Character, Integer> charToNum = new HashMap<>();
        int num = 9;
        for (Map.Entry<Character, Integer> entry : sortedWeights) {
            charToNum.put(entry.getKey(), num--);
        }
        
        // 4. 실제 숫자로 변환하여 합 계산
        int sum = 0;
        for (String word : words) {
            int number = 0;
            for (char ch : word.toCharArray()) {
                number = number * 10 + charToNum.get(ch);
            }
            sum += number;
        }
        
        // 5. 결과 출력
        System.out.println(sum);
    }
}

 

코드 설명

1. 가중치 계산

• 각 알파벳이 단어 내에서 차지하는 자리수를 반영하여 가중치를 계산합니다.
• 예를 들어 GCF의 경우:
  • G는 100의 자리 → 100
  • C는 10의 자리 → 10
  • F는 1의 자리 → 1
• 이를 모든 단어에 대해 수행하여 Map<Character, Integer>에 저장합니다.

2. 가중치가 높은 순서대로 정렬

• HashMap을 List로 변환한 후, 가중치를 기준으로 내림차순 정렬합니다.
• 가장 높은 가중치를 가진 알파벳부터 9, 8, 7, ... 순으로 숫자를 할당합니다.

3. 숫자로 변환 후 합산

• 각 단어를 숫자로 변환하고 최종 합을 구합니다.

 

시간 복잡도

• 가중치 계산: O(N * M) (N: 단어 개수, M: 단어 길이)
• 정렬: O(K log K) (K: 알파벳 개수, 최대 10)
• 숫자 변환 및 합산: O(N * M)
• 총 시간 복잡도: O(N * M + K log K) (최대 10!로도 충분히 빠름)