백준 1339번 단어수학 java

www.acmicpc.net/problem/1339

1339번: 단어 수학

분류 : 그리디

 

 

이 문제를 처음에는 완전탐색으로 접근했다가 바로 시간초과를 맞았다.

아무리 생각해도 풀이 방법이 생각나지 않아서 푸는 방법을 찾아보았다.

 

예시처럼 아래 두 문자열이 주어진다고 가정해보자.

GCF

ACDEB

 

이 문제의 정답은 'max'값을 찾는것이다. 따라서 높은 자릿수에 높은 값(9~0) 을 부여하면 된다.

GCF는 총 3자리이다. 따라서 100부터 시작한다.

100G, 10C, 1F 

 

ACDEB는 총 5자리이다. 따라서 10000부터 시작한다.

10000A, 1000C, 100D, 10E, 1B 

 

GCF의 값과 ACDEB의 값을 더해보자.

10000A, 1B, 1010C, 100D, 10E, 1F, 100G 이 나오게 된다.

 

나온 값을 26개의 int형 배열을 생성하여 넣어준후, 정렬한다. (26개를 생성한 이유는 A-Z가 총 26개이기 때문이다.)

 

높은값부터 9~0씩 곱하면 답을 구해낼 수 있다.

 

 

고수님들의 풀이 방법을 보면서 풀었는데, 어떻게 이런 생각을 스스로 해낼 수 있는지 정말 신기하고 존경스럽다...

 

-구현코드(JAVA)

import java.util.Arrays;
import java.util.Scanner;

public class 단어수학 {
    public static void main(String[] args) {
        
        //testcase 및 문자열 입력
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String [] arr = new String[n];
        int [] alpha = new int[26];
        for(int i=0; i<n; i++){
            arr[i] = sc.next();
        }


        for(int i=0; i<n; i++){
            int temp = (int)Math.pow(10,arr[i].length()-1);
            for(int j=0; j<arr[i].length(); j++){
                alpha[(int)arr[i].charAt(j)-65]+=temp;
                temp /=10;
            }
        }

        Arrays.sort(alpha);
        int index = 9;
        int sum =0;
        for(int i=alpha.length-1; i>=0; i--){
            if(alpha[i] == 0){
                break;
            }
            sum+= alpha[i]*index;
            index--;
        }
        System.out.println(sum);
    }
}