[백준] 1339 단어 수학 - 백트래킹 + 그리디 JAVA

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

1339번: 단어 수학

코드설명

백트래킹을 사용해서 풀거나 그리디 알고리즘을 사용해서 풀 수 있습니다.

 

저는 백트래킹을 활용해서 풀었습니다.

문제에서 중요한점은, simulate를 통해서 0~9까지의 값을 설정해주고,

그에 맞는 알파벳 Index를 알파벳의 종류를 중복처리한 ArrayList에 저장해두어서 0~9까지의 값을 백트래킹해서 넣어주어야합니다.

0~9까지의 값을 넣는것은 일반적인 백트래킹으로 진행하고,

ArrayList에 현재 존재하는 알파벳들의 Index를 처리하는것이 중요합니다.

alphabetValue[arr.get(level)] = i;

 

 

백트래킹을 사용시 시간초과가 걸렸었는데, 이유는 아래의 코드에서 Integer.parseInt 하는 과정에서 시간초과가 걸렸습니다.

int tempValue = 0;
for(int i=0;i<N;i++) {
    String str="";
    for(int j=0;j<words[i].length();j++) {
        str += alphabetValue[words[i].charAt(j) - 'A'];
    }
    tempValue += Integer.parseInt(str);
}
answer = Math.max(answer,  tempValue);

직접 값들을 처리하면서 진행했습니다.

아래와 같이 처리하는 것을 기억해두면 좋을 것 같습니다.

int value=0;
for(int i=0;i<N;i++) {
    int tempValue = 0;
    for(int j=0;j<words[i].length();j++) {
        tempValue *= 10;
        tempValue += alphabetValue[words[i].charAt(j) - 'A'];
    }
    value += tempValue;
}
answer = Math.max(answer,  value);

 

또한 이문제에서 백트래킹을 사용할때, 모든 알파벳을 검사하지않고 존재하는 알파벳만을 두고 조절하기 위해 ArrayList로 존재하는 알파벳을 중복처리하며 넣어줍니다. (arr.contains)  처음에 HashSet을 활용했었는데 HAshSet은 값의 순서를 보장하지않으므로 백트래킹에서 사용할 수 없습니다.

 

그리고서 아래코드와같이 

alphabetValue[arr.get(level)] 을 활용하여 각 알파벳의 인덱스에 값을 설정해줍니다.

for(int i=0;i<=9;i++) {
    if(visited[i] == false) {
        visited[i] =true;
        alphabetValue[arr.get(level)] = i;
        simulate(level + 1);
//        		alphabetValue[arr.get(level)] = 0;
        visited[i] = false;
    }

}

 

 

이 문제를 그리디로 푸는방식도 있었다는 점이 신기했습니다.

그리디로 푸는 로직은,

단어의 합의 최대값을 구하기 위해서는 

1. 가장 많이 나와야한다.

2. 가장 높은 자리에 위치해야한다.

라는 조건의 순서대로 가중치값을 부여합니다.

 

문제예시와 함께 살펴보겠습니다.

GCF

ACDEB 

 

GCF는 총 3자리입니다.

그러므로 100, 10 1 이렇게 값을 더해줍니다.

 

이떄 (int) Math.pow(10, 제곱 몇번할것인가) 를 활용해 10^3 이 값을 쉽게 구할 수 있습니다.

 

ACDEB는 총 5자리입니다.

10000, 1000, 100, 10, 1 을 더해줍니다.

 

그러면 자동으로 각 값들의 가중치의 합이 합해지고, 

Arrays.sort( alphabetValue ) 를 해주고, 

가장 높은 값들 순으로 9 ~ 0 값들을 곱해주면 값을 구할 수 있습니다.

 

코드

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

public class Main {
	
	public static int N;
	public static int answer = 0;
	public static String[] words;
	public static ArrayList<Integer> arr = new ArrayList<>();
	public static int alphabetKindCount = 0;
	public static int[] alphabetValue = new int[26];
	public static boolean[] visited = new boolean[10];
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	words = new String[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		words[i] = st.nextToken();
    		for(int j=0;j<words[i].length();j++) {
    			if( !arr.contains(words[i].charAt(j) - 'A')) { //중복처리 필요 ( 처음에 hashset썻었는데 순서를 보장안하기에 arr을 사용합니다.)
    				arr.add(words[i].charAt(j) - 'A'); 	
    			}
    			
    		}
    	}
    	
    	alphabetKindCount = arr.size();
    	
    	simulate(0);
    	System.out.println(answer);
    }
    
    public static void simulate(int level) {
    	if( level == alphabetKindCount) { //만약 모든 알파벳의 개수만큼 완료했다면, 종료.
    		int value=0;
    		for(int i=0;i<N;i++) {
    			int tempValue = 0;
    			for(int j=0;j<words[i].length();j++) {
    				tempValue *= 10;
    				tempValue += alphabetValue[words[i].charAt(j) - 'A'];
    			}
    			value += tempValue;
    		}
    		answer = Math.max(answer,  value);
            
    		return ;
    	}
    	
    	for(int i=0;i<=9;i++) {
    		if(visited[i] == false) {
    			visited[i] =true;
    			alphabetValue[arr.get(level)] = i;
        		simulate(level + 1);
//        		alphabetValue[arr.get(level)] = 0;
        		visited[i] = false;
    		}
			
    	}
    }
    
    
}

 

 

처음에 시간초과 난 코드

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

public class Main {
	
	public static int N;
	public static int answer = 0;
	public static String[] words;
	public static ArrayList<Integer> arr = new ArrayList<>();
	public static int alphabetKindCount = 0;
	public static int[] alphabetValue = new int[26];
	public static boolean[] visited = new boolean[10];
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	words = new String[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		words[i] = st.nextToken();
    		for(int j=0;j<words[i].length();j++) {
    			if( !arr.contains(words[i].charAt(j) - 'A')) {
    				arr.add(words[i].charAt(j) - 'A'); //아 이거 중복처리를 안하는구나!	
    			}
    			
    		}
    	}
    	
    	alphabetKindCount = arr.size();
    	
    	simulate(0);
    	System.out.println(answer);
    }
    
    public static void simulate(int level) {
    	if( level == alphabetKindCount) { //만약 모든 알파벳의 개수만큼 완료했다면, 종료.
    		
    		int tempValue = 0;
    		for(int i=0;i<N;i++) {
    			String str="";
    			for(int j=0;j<words[i].length();j++) {
    				str += alphabetValue[words[i].charAt(j) - 'A'];
    			}
    			tempValue += Integer.parseInt(str);
    		}
    		answer = Math.max(answer,  tempValue);
    		return ;
    	}
    	
    	for(int i=0;i<=9;i++) {
    		if(visited[i] == false) {
    			visited[i] =true;
    			alphabetValue[arr.get(level)] = i;
        		simulate(level + 1);
        		visited[i] = false;
    		}
			
    	}
    }
    
    
}