[백준] 1132번. 합(JAVA)

문제

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

---

풀이(39분)

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

public class Main {

    static int n;
    static Alphabet[] alphabet = new Alphabet[10]; // 0행: 등장 위치에 대한 값, 1행 : 등장 횟수  // 열  : 0 : A ~ 9 : J 인덱스
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine()); // N개의 수

        for(int i = 0; i < 10; i++){
            alphabet[i] = new Alphabet(0,0,i); // 알파벳 배열 초기화
        }
        Set<Integer> impossibleZero = new HashSet<>(); // 제일 앞자리에 와 0이 될 수 없는 수의 집합
        for(int i = 0; i < n; i++){
            String s = br.readLine();
            int idx = s.charAt(0) - 'A'; // 인덱스 맞추기
            alphabet[idx].value += (long) Math.pow(10, s.length() -1); // 자릿수 별로 10 추가
            alphabet[idx].count++;
            impossibleZero.add(idx);
            for(int j = 1; j < s.length(); j++){
                idx = s.charAt(j) - 'A';
                alphabet[idx].value += (long) Math.pow(10, s.length() - 1 - j); // 자릿수 별로 10 추가
                alphabet[idx].count++;
            }
        }

        Arrays.sort(alphabet);

        boolean useZero = true;
        for(int i = 0; i < 10; i++){
            if(alphabet[i].count == 0){
                useZero = false; // 0을 굳이 안 써도 됨.
            }
        }

        int[] num = new int[10];
        Arrays.fill(num, - 1);
        if(useZero){
            for(int i = 9; i >= 0; i--){
                if(!impossibleZero.contains(alphabet[i].idx)){ // 제일 앞자리가 아닌 것중에
                    num[alphabet[i].idx] = 0; // 제일 작은 값을 0으로 초기화
                    break;
                }
            }
        }

        int max = 9;
        for(int i = 0; i < 10; i++){
            if(num[alphabet[i].idx] == 0){ // 0인 것을 제외하고
                continue;
            }
            num[alphabet[i].idx] = max; // 나머지를 작아지게
            max--;
        }

        long sum = 0;
        for(int i = 0; i < 10; i++){
            long check = alphabet[i].value;
            int pow = 0;
            while(check > 0){
                if(check % 10 != 0){
                    sum += (check % 10) * num[alphabet[i].idx] * Math.pow(10, pow); // 자릿 수에 값을 곱하기
                }
                check /= 10;
                pow++;
            }
        }
        
        System.out.println(sum);
    }

    static class Alphabet implements Comparable<Alphabet>{
        long value; //값
        int count;
        int idx;

        public Alphabet(long value, int count, int idx) {
            this.value = value;
            this.count = count;
            this.idx = idx;
        }

        @Override
        public int compareTo(Alphabet o) {
            if(o.value != this.value){
                return Long.compare(o.value, this.value);
            }
            return o.count - this.count;
        }
    }

}

---

문제 풀이 전략

 

 

 

N개의 문자열을 입력받고, 각 알파벳에 대해 자릿값 계산 및 등장 횟수 기록.

• • 예를 들어 GCF라는 단어가 들어오면:
    • G는 백의 자리 → 100
    • C는 십의 자리 → 10
    • F는 일의 자리 → 1
    • 이 값을 해당 알파벳의 누적 가치에 더함.
• 0이 될 수 없는 알파벳 체크
  • 맨 앞글자로 등장한 알파벳은 0이 될 수 없음.
  • 이 정보를 Set에 저장하여 후에 0을 할당할 때 피함.
• 알파벳 가치 정렬
  • 각 알파벳에 대해 누적된 자릿값(value)을 기준으로 내림차순 정렬.
  • 동점일 경우 등장 횟수가 많은 순으로 정렬.
• 숫자 할당
  • 0부터 9까지의 숫자를 정렬된 알파벳에 차례로 할당.
  • 0은 맨 앞에 올 수 없는 알파벳에만 할당.
  • 만약 모든 알파벳을 사용하지 않아도 된다면, 0을 사용하지 않아도 됨.
• 합산
  • 각 알파벳에 할당된 숫자와 자릿값을 곱하여 전체 합을 계산함.

 

최종적으로 중요한 것은 자릿수에 대해 10의 제곱에 대한 가중치를 제공하면, 자릿수를 넘어가는 것도 추적 가능하다는 것이다!