[백준] JAVA - 1339.단어 수학

생각

주어진 입력에서 중복되는 알파벳을 제거하고 알파벳으로 순열을 만든다음, 이 알파벳을 0~9 로 치환하여 입력 알파벳들의 합이 최대가 되는 알파벳 순열을 찾는 문제입니다. 이 문제에서는 알파벳이 최대 10개이기 때문에 순열을 사용해서 풀수있습니다.

 

비트마스킹을 사용한 순열생성 코드를 만든 다음 내부에서 알파벳을 숫자로 치환하고 누적합을 계산해줬습니다. 알파벳을 숫자로 치환할때 Key = 알파벳, Value = 숫자인 HashMap을 만든다음 가장 큰 수(9,8,7,...) 부터 왼쪽에 할당했습니다. 이렇게 숫자를 줘야만 최대합을 찾을수있습니다.

 

HashMap에서 Key 타입을 Character로 정의했기때문에 알파벳의 합을 계산할때 charcter배열을 String으로 한번 치환한다음 마지막으로 정수형으로 변환해주었습니다.

 

의외로 문제에서 요구하는게 어렵진 않았는데 char 타입을 문자열로 만들고 다시 int형으로 바꿀때 계속 에러가 나서 파이썬이 갑자기 그리워졌습니다..ㅎㅎ 그래도 이번 문제로 char <-> string 을 확실하게 이해했습니다!!

Java code

package com.java.algorithm;

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

public class Baekjoon_1339_단어수학 {
	static int N;
	static Character[] result;
	static List<Character> alphabet;
	static List<String> input;
	static HashMap<Character, Character> dict;
	static int ans = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		alphabet = new ArrayList<Character>();
		result = new Character[10];
		input = new ArrayList<String>();
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			input.add(temp);
			for (int j = 0; j < temp.length(); j++) {
				//중복 체크
				if(dupicateCheck(temp.charAt(j))) {
					alphabet.add(temp.charAt(j));
				}
				
			}
		}
		//solve
		permutation(0, 0);

		System.out.println(ans);
		

	}
	
	private static boolean dupicateCheck(char c) {
		for (int i = 0; i < alphabet.size(); i++) {
			if(alphabet.get(i) == c) return false;
		}
		return true;
	}

	private static void permutation(int cnt, int flag) {
		if(cnt == alphabet.size()) {
			
			//앞에서부터 차례대로 9,8,7 숫자 생성
			//{알파벳 : 숫자} hashmap
			int sum = 0;
			dict = makeNumber(result);
			for (int i = 0; i < input.size(); i++) {
				char[] temp = new char[input.get(i).length()];
				for (int j = 0; j < input.get(i).length(); j++) {
					//숫자를 문자열로 인식한다음 누적합계산해야한다..
					char c = dict.get(input.get(i).charAt(j));
					temp[j] = c;
				}
				String s = new String(temp);
				sum += Integer.parseInt(s);
				
			}
			
			
			ans = Math.max(ans, sum);
			return;
		}
		for (int i = 0; i < alphabet.size(); i++) {
			if((flag & 1<<i) != 0) continue;
			result[cnt] = alphabet.get(i);
			permutation(cnt+1, flag | (1<<i));
		}
	}

	private static HashMap<Character, Character> makeNumber(Character[] arr) {
		int num = 9;
		HashMap<Character, Character> result = new HashMap<>();
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] == null) continue;
			result.put(arr[i], (char)(num-- + '0'));
		}
		return result;
		
	}

}