BOJ - 단어 수학 1339번 (JAVA)

❓ 문제 - 백준 단어 수학 1339번 - JAVA 풀이법

출처

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

1339번: 단어 수학

 

 

 

📝 문제해결법

1. 문제

• 알파벳 대문자를 0~9의 숫자로 치환할 때, 모든 알파벳을 더한 값이 최대값이 되도록 각 알파벳에 할당될 숫자를 정해야한다.
• 따라서 선정된 알파벳 숫자에 의해 더한 값의 최대값을 정답으로 출력한다.

 

2. 해결 방법

• 그리디 알고리즘의 방법으로 문제를 접근한다.
• 각 알파벳은 각각의 자릿수가 있으므로 주어진 알파벳 인덱스에 해당하는 곳에 자릿수를 계속 더한다.

예를 들어, ABC 라고 할 때 A는 alpha 인덱스에 0번이고 alpha[0]에는 100이 더해져 있다. B는 alpha 인덱스에 1번이고 alpha[1]에는 10이 더해져 있다. C는 alpha 인덱스에 2번이고 alpha[2]에는 1이 더해져 있다. 다음 AB를 입력받는다면, alpha[0] += 10 alpha[1] += 1 이 더해진 상태로 되어 있을 것이다.

• 위와 같은 상태로 alpha를 계속 더한 후에, alpha를 정렬해주고 값이 가장 큰 값부터 숫자 9 부터 할당해준다.
• 따라서 숫자를 할당해준 후, 각 자릿수에 있는 숫자 x 자릿수 값 x 할당된 값을 answer에 계속 더해가면 답을 구할 수 있게된다.

 

 

3. 느낀점

• 처음에 리스트랑, 해쉬를 사용해서 구현이 복잡하도록 풀이를 생각했는데.. 이건 도저히 아닌 것 같아서 다른 사람들의 풀이를 봤다. 그리디 알고리즘 답게 심플한 풀이법을 잡아서 해결해야했다...
• 그리디 문제들을 많이 풀면서 해결방법의 센스를 좀 높이도록 노력해야지..!

 

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main_1339 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long[] alpha = new long[26];
        for(int i=0;i<n;i++){
            String str = br.readLine();
            for(int j=0;j<str.length();j++){
                alpha[str.charAt(j) - 'A'] += Math.pow(10, str.length()-j-1);
            }
        }

        Arrays.sort(alpha);
        int num = 9;
        long answer = 0;
        for(int i=25;i>=0;i--){
            if(alpha[i] == 0) continue;
            String s = String.valueOf(alpha[i]);
            char[] c = s.toCharArray();
            for(int j=0;j<c.length;j++){
                if(c[j] == '0') continue;
                answer += (c[j]-'0') * num * Math.pow(10, c.length-j-1);
            }
            num--;
        }

        System.out.println(answer);


    }
}