백준 1339번 <단어 수학>

백준 알고리즘 1339번

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

1339번: 단어 수학

---

1339번

입력으로 첫 줄에는 단어의 개수 N이 들어오고 그 다음 N줄에 걸쳐 알파벳 대문자로 이루어진 단어가 주어진다.

 

출력은 N개의 단어를 숫자로 만들었을 때, 그 수의 합의 최대를 출력한다.

(단어를 숫자로 만드는 방법은 각 알파벳을 하나의 숫자로 치환하는 것이다.)

---

문제 해결

처음에는 가장 높은 자릿수에 오는 알파벳에 가장 큰 숫자를 부여하는 방식으로 풀었다.

그랬더니

2

AB

BB

이런 케이스에 대해 정답을 구하지 못했다.

 

그래서 단어에서 알파벳의 위치를 자릿수로 만들어서 알파벳의 숫자를 저장해뒀다.

2

AB

BB

가 들어왔다고 하면

A 10

B 12

이런 식으로 저장했다.

그러면 A보다 B가 크기 때문에 B를 9로 하고 A를 8로 하면 된다.

---

코드

package bj1339;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		PriorityQueue<Integer> pq = new PriorityQueue<>();

		String str = br.readLine();
		int n = Integer.parseInt(str);

		int[] alpha = new int[26];
		for (int i = 0; i < 26; i++) {
			alpha[i] = 0;
		}

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

		for (int i = 0; i < 26; i++) {
			if (alpha[i] == 0)
				continue;
			pq.add((-1) * alpha[i]);
		}

		int idx = 9;
		int answer = 0;
		while (!pq.isEmpty()) {
			int a = (-1) *  pq.poll();
			answer += a * idx;
			idx--;
		}
		System.out.println(answer);

	}

}

---

결과

---