알고리즘 풀이 - 백준 1339(단어 수학, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

 

N개의 단어가 주어질 때, 각 단어의 자리는 대문자 알파벳으로 주어지며 0~9로 치환이 가능 시, 모든 단어를 더했을 때 가장 최대의 값이 되는 결과를 구하는 문제

 

 

2. 풀이

 

우선 주어지는 알파벳 리스트를 저장하고 각 알파벳에 숫자를 치환시켜 더해보고 최대값을 구하여 출력하는 문제이다.

두 가지의 풀이 방법이 있다.

① 완전 탐색을 통해 가능한 숫자를 모두 대입하여 풀기
② 그리디 알고리즘 사용하기

 

① 완전 탐색으로 풀기

이 방식은 문제를 해결할 수는 있지만 시간이 오래 걸린다. 예를 들어 ABC, BCD 라는 단어가 있다고 가정하자. 그러면 알파벳 리스트는 다음과 같이 정리된다.

알파벳 리스트 : [A, B, C, D]

위의 알파벳 리스트를 중복 없이 저장한 뒤, 4개이므로 9, 8, 7, 6의 4개의 숫자로 치환할 수 있을 것이다.(혹은 6, 7, 8, 9의 순서대로)

단어의 길이는 최대 10자리이며 다양한 길이의 단어가 주어질 수 있으므로 어떤 치환 방식이 가장 큰 결과를 만들 수 있는지를 계산해야 한다.

그 방법은 순열을 이용하여 모든 방법을 수행해보는 것이다. [6, 7, 8, 9]로 치환했다면 [9, 8, 7, 6]까지 모든 경우를 다 대입해서 진행하는 것이다. 이를 통해 결과를 출력한다.

 

② 그리디 알고리즘으로 풀기

그리디 알고리즘은 현재의 상황에서 최선의 경우를 무조건 선택하여 문제를 해결하는 방식이다. 그래서 반드시 그 결과가 최적이 되게 할 보장은 없다.

그러나 이 문제는 수학적으로 항상 최적의 결과를 내도록 그 결과를 만들 수 있다. 위의 예시 처럼 ABC, BCD의 단어가 있다고 가정하자.

그러면 각 숫자에 1을 대입한다고 할 때, 각 숫자가 만들 수 있는 값은 다음과 같다.

A : 100
B : 10 + 100 = 110
C : 1 + 10 = 11
D : 1

따라서, B가 가장 큰 결과를 만들고 차례대로 A, C, D가 그 뒤를 잇게 된다. 그래서 8, 9, 7, 6의 순서로 대입하면 가장 큰 숫자를 만들 수 있게 된다.(답 : 1873)

즉, 모든 단어의 알파벳을 통해 그 자리수를 곱하여 해당 숫자를 모두 더할 시 만들 수 있는 가장 큰 값을 계산하여 정렬한 뒤 9부터 차례대로 숫자를 대입하고 그 결과를 출력하면 끝나는 문제이다.

이 방식은 매우 빠른 속도로 해결할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

① 완전 탐색 사용하기

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

public class Main{
    static int n;
    static String[] words;  // 주어진 단어를 저장
    static List<Character> list; // 알파벳 리스트 저장
    static int[] nums;  // 알파벳 치환시킬 숫자들 저장
    static int max = 0; // 마지막에 출력할 최대값
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        words = new String[n];
        list = new ArrayList<>();

        // 주어진 단어 기반, 알파벳들을 저장한다.(이미 저장된 것은 제외)
        for(int i=0; i < n; i++){
            words[i] = br.readLine();
            for(int j=0; j < words[i].length(); j++){
                // 아래 코드로 이미 저장된 것 제외하고 추가
                if(!list.contains(words[i].charAt(j))){
                    list.add(words[i].charAt(j));
                }
            }
        }

        // 알파벳 숫자 개수 크기로 배열을 만들고 9부터 넣을 수 있는 가장 큰 숫자를 넣는다.
        nums = new int[list.size()];
        int val = 10 - list.size();  // 2개면 8, 9를 넣어야 하므로 8부터 시작
        for(int i=0; i < list.size(); i++){
            nums[i] = val;
            val++;
        }

        // 다음 순열을 구할 수 없을 때까지 반복하여 문제를 해결
        while(true){
            check();
            if(!perm()) break;
        }
        System.out.println(max);
        br.close();
    }

    // 다음 순열을 구하는 메소드
    private static boolean perm(){
        int i = nums.length-1;
        while(i > 0 && nums[i-1] >= nums[i]) i--;
        if(i <= 0) return false;

        int j=i-1;
        while(j < nums.length-1 && nums[j+1] > nums[i-1]) j++;
        swap(i-1, j);

        j = nums.length-1;
        while(i < j){
            swap(i, j);
            i++; j--;
        }
        return true;
    }
    private static void swap(int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    // 각 단어의 알파벳을 통해 index를 구하고 저장된 숫자를 곱하여 전체 최대값을 구한다.
    private static void check(){
        int val = 0;
        for(String word : words){
            // 현재 단어 크기만큼의 배수를 미리 계산
            int d = (int)Math.pow(10, word.length() - 1);
            for(int j=0; j < word.length(); j++){
                val += (nums[list.indexOf(word.charAt(j))] * d);
                d /= 10;
            }
        }
        
        // 출력할 최대값과 비교
        max = Math.max(val, max);
    }
}

 

② 그리디 알고리즘으로 풀기

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

public class Main{
    static int n;
    static int[] alp = new int[26]; // 각 알파벳이 나온 자리수에 따라 값을 더하여 저장하는 배열
    static String[] words;
    static int ans = 0;
    public static void main(String[] args) throws IOException{

        // ********************** 주어진 값, 문자 저장 ***********************
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        words = new String[n];
        int k = 0;
        for(int i=0; i < n; i++){
            String word = br.readLine();

            // 문자 저장
            words[i] = word;

            int d = 1;
            // 서로 문자열 나온 상태에 따라 자리수 만큼 더하여 배열 내 저장
            for(int j=word.length()-1; j >= 0; j--){
                int c = word.charAt(j) - 'A';
                alp[c] += d;
                d *= 10;
            }
        }
        // ********************** 주어진 값 저장 완료 ************************


        // ********************** 계산 수행 *****************************
        Arrays.sort(alp);  // 저장된 배열 정렬
        int idx = 0;
        
        // 각 숫자에 9부터 시작하여 큰 수부터 대입시키며 더해준다.
        for(int i=9; i >= 0; i--){
            ans += alp[25 - idx] * i;
            idx++;
        }
        System.out.println(ans);
        // ********************** 계산 완료 *****************************
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.