[그리디] 백준 1339번 단어수학 - JAVA

 

 

 

 

---

1. 출처

---

 

 

1339번: 단어 수학

 

 

 

 

 

이 문제는 내 머릿속으로는 너무 복잡하게 설계가 되어서 30분 정도 삽질하다가 결국 설계안을 찾아봤다. 똑똑한 설계안이 있어서 나는 그 설계안을 이해하고, 내 코드로 만들었다. 오늘부터는 BufferedReader를 사용해 입력을 받아 시간을 줄여볼 예정이다.

 

 

 

---

2. 설계

---

 

결국 가장 높은 합을 가져야 하는건데...

가장 높은 합 즉, 값을 가지려면 큰 자릿수에 있는 알파벳에 높은 수가 매칭되어야한다.

 

 

아이디어는 알고나면 간단하다.

하나에 알파벳에 할당되는 수는 같으니 하나의 알파벳에 나올 수 있는 자릿수를 모두 더해 리스트에 저장하자는 뜻이다.

 

 

이해가 안된다면 예제를 보자!

만약 AAA라는 문장이 들어왔다면, 각 자릿수는

 

A(100) A(10) A(1)일 것이다. 이것들을 쪼개서 모두 더해 A를 담당하는 Index에 아래처럼 모두 더해주자는 뜻이다.

 

 

 

 

 

만약 다음에 같은 문장 AAA가 나온다고 하더라도 같은 INDEX에 계속 나오는 자릿수를 더해주면 된다.

 

 

 

이렇게 모든 알파벳이 가질 수 있는 자릿수가 더해졌다면, Arrays.sort를 이용해 정렬하고 가장 큰 값부터 큰 수를 할당해 곱해주면 된다. 예를 들어 A가 가장 큰 값이면 9를 곱해주면 된다. (222 X 9 = 1998)

 

 

---

3. 전체코드

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //2

        int[] alpha_list = new int[26];//각 알파벳은 어떤 자릿수를 가지고 있는지 확인

        for(int i=0; i<N; i++){
            String sentence = br.readLine();//AAA

            int position10 = (int)Math.pow(10, sentence.length()-1);
            
            for(int j=0;j<sentence.length();j++){
                
                int alpha = sentence.charAt(j)-65;

                alpha_list[alpha] += position10; //특정 알파벳이 가지는 모든 자릿수를 더해준다.
                position10/=10;
            }
        }

        Arrays.sort(alpha_list);

        int num = 9;
        int sum = 0;
        for(int i=25; i>=0; i--){
            sum+=alpha_list[i]*num;
            num--;
        }

        System.out.println(sum);
    }
}