백준(1132번) - 합 (Java) (그리디)

테스트 케이스 1을 기준으로 설명을 해보겠다.

 

ABC

BCA

위를 살짝 풀어써보면 A = 101 * M / B = 110 * N / C = 11* O 이 3가지를 더해준 것이다.

 이렇게 생각해 보면 당연히 큰 수가 될 B의 N이 9가 되고, A의 M이 8이 되고, C의 O가 7이 되는 게 최댓값이 될 것이다. 실제로 그렇게 해주면 되지만 살짝 꼬아놓은 것이 첫자리에 0은 못 온다는 제약을 걸어 놓은 것이다.

 

그렇게 처음에 구현한 것이 이거였다.

import java.util.*;
import java.io.*;


public class Main
{
	static int n;
	static long[] alpha = new long[10];
	static boolean[] first = new boolean[10];
	static boolean[] use = new boolean[10];
	static long ans;
	
	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 sick = br.readLine();
			
			for(int j = 0 ; j < sick.length() ; j++)
			{
				alpha[sick.charAt(j) - 'A'] += (long)Math.pow(10,sick.length()-1-j);
				
				if(j == 0) first[sick.charAt(j) - 'A'] = true;	//앞 자리에 등장
			}
		}
		
		Arrays.sort(alpha);
			
		for(int i = 0 ; i < 10 ; i++)
		{
			if(first[i])
			{
				for(int j = 1 ; j < 10 ; j++)
				{
					if(!use[j])
					{
						use[j] = true;
						ans += (alpha[i] * j);
						break;
					}
				}
			}
			else
			{
				for(int j = 0 ; j < 10 ; j++)
				{
					if(!use[j])
					{
						use[j] = true;
						ans += (alpha[i] * j);
						break;
					}
				}
			}
		}
		
		System.out.println(ans);
	}

}

그저 문제가 없을 것이라고 생각했으나, 문제는 first는 따라오지 않는다는 거...

 

그래서 class를 이용해 배열을 만들어서 해결했다.

<문제>

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

 

<소스코드>

import java.util.*;
import java.io.*;


import java.util.*;
import java.io.*;


public class Main
{
	static class node implements Comparable
	{
		long num;
		boolean first;
		
		public int compareTo(node o) 
		{
			if(num>o.num)
			{
				return 1;
			}
			if(num==o.num)
			{
				return 0;
			}
			else
			{
				return -1;
			}
		}
	}
	
	static int n;
	static boolean[] use = new boolean[10];
	static long ans;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		node[] alpha = new node[10];
		for(int i = 0 ; i < 10 ; i++) alpha[i] = new node();
		
		for(int i = 0 ; i < n ; i++)
		{
			String sick = br.readLine();
			
			for(int j = 0 ; j < sick.length() ; j++)
			{
				alpha[sick.charAt(j) - 'A'].num += (long)Math.pow(10,sick.length()-1-j);
				
				if(j == 0) alpha[sick.charAt(j) - 'A'].first = true;
			}
		}
		
		Arrays.sort(alpha);
		
		for(int i = 0 ; i < 10 ; i++)
		{
			if(alpha[i].first)
			{
				for(int j = 1 ; j < 10 ; j++)
				{
					if(!use[j])
					{
						use[j] = true;
						ans += (alpha[i].num * j);
						break;
					}
				}
			}
			else
			{
				for(int j = 0 ; j < 10 ; j++)
				{
					if(!use[j])
					{
						use[j] = true;
						ans += (alpha[i].num * j);
						break;
					}
				}
			}
		}
		
		System.out.println(ans);
	}

}