[백준] 1339번 - 단어 수학 (Java)

풀이

키워드

• 그리디 알고리즘

  단어의 합의 최댓값을 구하기 위해서는 (1. 가장 많이 나오고) (2. 가장 높은 자리에 위치) 한 순서대로 가장 높은 숫자를 부여하면 된다. 그때 그때  가장 최선의 경우를 구해야 하므로 그리디 알고리즘임을 쉽게 알 수 있다.

  따라서 우리는 가장 많이 나오고 가장 높은 자리에 위치한다는 것을 어떻게 정할지만 정하면 된다. 문자를 수로 치환하여 가장 큰 값을 찾아야 하므로, 각 문자마다 위치한 수의 자리에 따라 가중치를 정해서 더해주면 된다.

 

  예를 들어, AAA, ACDEB 가 있다고 해보자.

•   AAA
  • A는 100의 자리, 10의 자리, 1의 자리에 해당하는 가중치를 가진다.
  • 따라서 A += 100 + 10 + 1
• ACDEB
  • ACDEB = 10000 + 1000 + 100 + 10 + 1로 나타낼 수 있다.
  • 따라서 A += 10000, C += 1000, D += 100, E += 10, B += 1
• 연산을 하면 A=10111, B = 1, C = 1000, D = 100, E = 10 이 된다.

  이제 이 가중치가 높은 순서대로 9, 8, 7, ...을 곱해주자.

  여기서 알 수 있듯이, 특정 알파벳에 얼만큼의 가중치가 있는지는 신경 쓸 필요가 없다. 우리에게 필요한 것은 크기순으로 나열된 가중치들이다.

 

10111*9 + 1000*8 + 100*7 + 10*6 + 1*5 이므로 답은  99764 이다.

---

코드

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


public class Main2 {
	static int N;
	static int [] arr = new int[26];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < str.length(); j++) {
				char c = str.charAt(j);
				arr[c-'A'] += (int)Math.pow(10, str.length() - 1 - j);
			}
		}
		
		Arrays.sort(arr);
		
		int num = 9;
		int turn = 25;
		int ans = 0;
		while(arr[turn] != 0) {
			ans += arr[turn]*num;
			turn--;
			num--;
		}
		
		System.out.print(ans);
	}
}

 

---

출처 : www.acmicpc.net/problem/1339

1339번: 단어 수학