[그리디] 1339. 단어 수학

[BOJ] 1339. 단어 수학

주어진 단어들에서 각 문자에 숫자를 할당하여 최대 합을 구하는 문제이다.

📌 그리디 풀이 과정

• 알고리즘: 이 코드는 그리디(greedy) 알고리즘을 사용하여 가장 높은 가중치를 가진 문자에 높은 숫자를 할당하는 방식이다.
• 로직:
  1. 각 문자가 해당 위치에서 가지는 가중치(자리수에 따른 중요도)를 계산하여 alpha 배열에 저장한다.
  2. alpha 배열을 내림차순으로 정렬한다.
  3. 가중치가 큰 문자부터 9, 8, 7... 순으로 숫자를 할당하여 최대 합을 계산한다.
  4. 이 접근법은 가능한 조합을 전부 탐색하지 않지만, 대부분의 경우 최적해에 가까운 결과를 빠르게 구할 수 있다.
  5. 시간 복잡도는 O(N * M) 정도로, N은 단어의 수, M은 단어의 길이이다. 순열 방식에 비해 훨씬 효율적이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
		int[] alpha = new int[26];
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < str.length(); j++) {
				alpha[str.charAt(j) - 'A'] += (int)Math.pow(10, str.length() - j - 1);
			}
		}
		
		Arrays.sort(alpha);
		
		int sum = 0;
		int idx = 25;
		int num = 9;
		while(alpha[idx] > 0) {
			sum += alpha[idx] * num;
			idx--;
			num--;
		}
		
		System.out.println(sum);
	}

}

📌 순열 풀이 과정

• 알고리즘: 이 코드는 순열(permutation) 알고리즘을 사용하여 가능한 모든 숫자 할당 조합을 탐색하고, 그중에서 가장 큰 합을 구하는 방식이다.
• 로직:
  1. 먼저 주어진 단어들에서 사용된 모든 문자를 리스트에 저장한다.
  2. 이 리스트의 문자를 숫자 0~9 중 하나로 매핑하는 모든 가능한 조합을 생성한다.
  3. 각 조합에 대해 주어진 단어들을 숫자로 변환하여 합계를 계산한다.
  4. 모든 조합 중 가장 큰 합을 max 변수에 저장하여 출력한다.
  5. 시간 복잡도는 리스트에 포함된 문자의 수에 따라 기하급수적으로 증가한다. 따라서 리스트의 문자가 많을수록 비효율적일 수 있다.

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

public class Main {
	
	static int N;
	static int max = Integer.MIN_VALUE;
	static List<Character> list;
	static String[] word;
	static int[] value;
	static boolean[] visited;
	

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		list = new ArrayList<>();
		word = new String[N];
		
		for(int i = 0; i < N; i++) {
			word[i] = br.readLine();
			for(int j = 0; j < word[i].length(); j++) {
				if(!list.contains(word[i].charAt(j))) list.add(word[i].charAt(j));
			}
		}
		
		value = new int[list.size()]; // 각 문자에 할당된 숫자 저장하는 배열
		visited = new boolean[10]; // 0 ~ 9 숫자 사용 여부
		permutation(0);
		
		System.out.println(max);
	}
	
	private static void permutation(int cnt) {
		if(cnt == list.size()) {
			int sum = 0;
			for(int i = 0; i < N; i++) {
				int num = 0;
				for(int j = 0; j < word[i].length(); j++) {
					num *= 10;
					num += value[list.indexOf(word[i].charAt(j))];
				}
				sum += num;
			}
			max = Math.max(max, sum);
			return;
		}
		
		for(int i = 0; i <= 9; i++) {
			if(visited[i]) continue;
			
			visited[i] = true;
			value[cnt] = i;
			permutation(cnt + 1);
			visited[i] = false;
			value[cnt] = 0;
		}
	}

}