[백준] code.plus(브루트포스 - 순열,JAVA)1339번, 단어 수학

문제 링크

1339번: 단어 수학

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

이 문제에 핵심은

1. N개의 단어는 항상 알파벳 대문자의 형태입니다.

2. 입력되는 단어들에 사용된 알파벳에 0~9까지 숫자를 부여합니다.

3. 단어들에 숫자를 대입하여 단어들의 합을 결과로 출력합니다.

 

 

제가 처음에 문제를 해결했던 코드입니다.

 

입력되는 단어들에 사용되는 알파벳 대문자들을 List와 HashMap에 저장하였습니다.

 

알파벳에 부여할 수 있는 숫자의 경우를 모두 구하여 단어에 대입하여 합이 최대인 값을 결과로 출력하였습니다.

import java.io.*;
import java.util.*;
public class Main {
	static int N;
	static ArrayList<String> word = new ArrayList<>();	//단어 저장 리스트
	static ArrayList<Character> alphabetList = new ArrayList<>();	//사용된 알파벳 리스트
	static HashMap<Character,Integer> alphabet = new HashMap<>();	//알파벳 해쉬맵
	static int result = Integer.MIN_VALUE;		//결과
	static boolean[] numCheck = new boolean[10];	//숫자 사용 확인
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	N = Integer.parseInt(br.readLine());
        //단어 및 알파벳 저장
    	for(int i=0;i<N;i++) {
    		String temp = br.readLine();
    		word.add(temp);
    		for(int j=0;j<temp.length();j++) {
    			if(!alphabet.containsKey(temp.charAt(j))) {
    				alphabet.put(temp.charAt(j),0);
    				alphabetList.add(temp.charAt(j));
    			}
    		}
    	}
    	cal(0, alphabet.size());	//함수 실행
    	bw.write(result + "\n");	//결과 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //재귀를 통해 알파벳의 모든 경우의 수를 구하여 단어의 합을 비교하는 함수
    static void cal(int index, int alphabetSize) {
    	if(index == alphabetSize) {		//모든 알파벳 숫자 부여시
    		getWordValue();		//단어에 대입하여 합 비교
    		return;
    	}
        //알파벳에 0~9 숫자 부여
    	for(int i=9;i>9-alphabetSize;i--) {
    		if(numCheck[i])
    			continue;
    		alphabet.put(alphabetList.get(index), i);
    		numCheck[i] = true;
    		cal(index+1,alphabetSize);
    		alphabet.put(alphabetList.get(index), 0);
    		numCheck[i] = false;
    	}
    	return;
    }
    //알파벳 숫자 단어에 대입하여 합 비교하는 함수
    static void getWordValue() {
    	int value = 0;
        //단어의 합 구하기
    	for(int i=0;i<word.size();i++) {
    		String str = word.get(i);
    		int temp = 0;
    		for(int j=0;j<str.length();j++) {
    			temp*=10;
    			temp += alphabet.get(str.charAt(j));
    		}
    		value += temp;
    	}
        result = Math.max(result, value);	//현재 최대값과 비교하기
    }
}

위 코드에서 통과는 했지만 시간이 2600ms 정도로 많이 소모됩니다.

 

그래서 다른 사람들의 코드을 참고하여 수정해보았습니다.

 

예제입력 2의 입력값을 아래와 같이 바꿀 수 있습니다.

GCF = 100G + 10C + F 
ACDEB = 10000A + 1000C + 100D + 10E + B

GCF + ACDEB = 10000A + 1010C + 100D + 100G + 10E + B

 

A=9, B=8, C=7, D=6, G=5, E=4, B=3일 때 최대값이 됩니다.

 

위 규칙을 이용하기 위해서 A-Z까지의 값들을 배열에 저장한 뒤

입력되는 단어에 따른 값들을 배열에 저장합니다

 

alphabet[0] = A의 대한 값 = 10000

alphabet[1] = B의 대한 값 = 10

....

 

저장한 뒤 오름차순으로 정렬하여 alphabet[25]의 값부터 높은 숫자를 부여하면 구하실 수 있습니다.

import java.io.*;
import java.util.*;
public class Main {
	static int N,result=0;
	static int[] alphabet = new int[26];
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	N = Integer.parseInt(br.readLine());
    	for(int i=0;i<N;i++) {
    		String word = br.readLine();
    		int length = (int)Math.pow(10, word.length()-1);
    		for(int j=0;j<word.length();j++) {
    			alphabet[word.charAt(j)-65] += length;
    			length /= 10;
    		}
    	}
    	Arrays.sort(alphabet);
    	for(int i=25;i>15;i--) {
    		result += alphabet[i] * (i-16);
    	}
    	bw.write(result + "\n");
    	bw.flush();
    	bw.close();
    	br.close();
    }
}

 

두 코드의 시간 차이

2608ms = 처음 제가 작성했던 코드

144ms = 다른 사람들의 코드를 참고하여 작성한 코드