[ BOJ 1339] 단어 수학 (Java)

BOJ 1339 단어 수학

문제풀이

문제는 굉장히 간단했다. 단순히 주어진 문자에 대한 문자 - 숫자 매핑의 모든 경우를 만들고 그에 대한 합계 최댓값을 구하는 것이다. 하지만, 이 문제에서 다시 한번 String을 직접 사용하는 것이 얼마나 부담이 큰지 느끼게 되었다.

• 주어진 문자들의 중복을 제거하기 위해 HashSet 사용
• 문자 - 숫자 매핑의 번거로움과 효율을 위해 HashMap 사용
• 한 자리씩 추가하는 숫자의 경우에 문자로 바꾸기 보다 *10의 방법을 사용하자

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Main {
	static char[][] input;
	static HashSet<Character> set;
	static HashMap<Character, Integer> map;
	static ArrayList<Character> alphabet;
	static boolean[] selected;

	static int N, max;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		max = Integer.MIN_VALUE;
		set = new HashSet<>();
		map = new HashMap<>();
		input = new char[N][];
		
		for(int i = 0 ; i < N ; ++i) {
			char[] line = br.readLine().toCharArray();
			// 원래 알파벳을 기억한다. 
			input[i] = line;
			// 주어진 알파벳을 set에 넣는다.(중복제거) 
			for(char c : line) set.add(c);
		}
		
		alphabet = new ArrayList<>(set);
		
		selected = new boolean[10];
		permutation(0);
		
		System.out.println(max);
	}
	
	private static void permutation(int depth) {
		if(depth == alphabet.size()) {
			int temp = calc();
			max = temp > max ? temp : max;
			return;
		}
		
		for(int i = 0 ; i < 10 ; ++i) {
			if(!selected[i]) {
				selected[i] = true;
				// 해쉬맵으로 문자 - 숫자를 매핑한다.
				map.put(alphabet.get(depth), i);
				permutation(depth + 1);
				selected[i] = false;
			}
		}
		
	}

	// 매핑된 문자 - 숫자를 바탕으로 합계 산출하기 
	private static int calc() {
		int result = 0;
		
		for(int i = 0 ; i < N ; ++i) {
			int temp = 0;
			// String을 직접 핸들링하는 것은 부담이 크다(연산, 파싱) 
			for(char c : input[i]) {
				temp *= 10;
				temp += map.get(c);
			}
			result += temp;
		}
		
		return result;
	}
}