[백준] 1339 단어수학

1339번: 단어 수학

문제 이해하기

단어수학 문제는, N개의 단어로 이루어짐.

• 단어의 , “각” 알파벳 대문자를 0 ~ 9 의 숫자 중, 하나로 바꿔, N개의 수를 합하는 문제다.

무슨 말이냐면

“GCF” 라는 단어와 “ACDEB” 라는 단어가 있을 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정 한다면 → 두 수의 합은 : 783 + 98654 = 99437 이 된다. 그리고 이와 같이, 각 알파벳에 값을 지정했을 때가 두 수의 합이 최대가 되는 때이다.

• 두 개이상의 알파벳이 같은 숫자로 바뀌어지지는 않는다.
  • 그렇다면, 숫자는 0~9까지이니, 알파벳의 종류가 최대 10개로 주어지겠다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램???

(방향이 잘못된)문제 풀이하기 ( 힌트가 되는 생각이긴 하나 ,잘못된 풀이생각이니 패쓰해줄것..)

일단 여기서 생각나는 것이 하나 있다.

1. 단어의 길이가 더 긴 단어의, 앞자리에 위치한 알파벳일 수록 큰 값이 매칭되어야 한다.
   • 예를들어 GCF 와 ABGDE 라면 → A가 가장 큰 값, B가 다음, G가 그 다음 ... 이런식이 되어야한다.
2. 또, 같은 자리 수의 서로다른 알바벳에 대하여는, 해당 자리에 더 자주등장한 알파벳이 더 큰 값을 가져야함.
   • 예를들어, ADE 와 CE DG 라면, A는 9를 갖는다. C와 D 모두 10의 자리 수이지만, D가 10의 자리에 2번 등장하고, C가 1 번 등장하였으니 D가 8, C가 7 이어야한다.
   • 그리고 이 조건을 사용할 수 있는 것은, 단어의 총 개수가 10개 이하이기 때문인 것 같다. ( 왠지 그런것 같은데, 일단 이건 나중에 생각 )
3. 같은 자리수의 서로 다른 알파벳이, 같은 횟수 등장 한다면 → 다음 자리에서 더 자주 등장한 것이 더 큰 값을 갖도록 해야한다. → while문으로 풀어내야 한다.

• 그리디하게 풀어야 하는데

완전 잘못 생각하고 풀고 있었다.

이거 그냥 location 별로 나누고 곱하고 더해서 그 크기로 정렬하면 되는 것 같다...ㅠㅠㅠ....하.. 갑자기 생각났다.

무슨 말이냐면, alphabet 별로, 미리 값을 다 계산해 둔다. 예를들어

ABGDE 와 GCF라면

A : 10000

B : 1000

C : 10

D : 10

E : 1

F : 1

G : 200

이 되는 것이다. → 그러면 이 값 순으로 정렬을 해서, 큰 값을 가지는 애한테 큰 값을 할당해 주면 되는 것이다.

큰 자리수라고 무조건 큰 값을 할당해야한다고 생각하면 틀리게 된다.

그리고 그 할당된 값을 곧바로 곱하고 더해주고 하면 바로 문제에서 원하는 결과값까지도 구할 수가 있다.

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

public class Main{
    public static int len = 'z'-'a'+1;
    public static int n;
    public static int[] alphaValue = new int[len];
    public static int[] alphaCnt = new int[len];

    public static class Element{
        public int ch; // character
        public int val; // count 값 ex)10000 2000.. 이런거

        public Element(int ch, int val) {
            this.ch = ch;
            this.val = val;
        }
    }

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void setting() throws IOException {
        n = Integer.parseInt(br.readLine());
        String temp = null;
        int pow = 1;
        for (int i = 0; i < n; i++) {
            temp = br.readLine();
            for(int idx = 0 ; idx< temp.length();idx++){
                pow = (int)Math.pow(10,temp.length()-idx-1);
                alphaCnt[temp.charAt(idx)-'A'] += pow;
            }
        }
    }
    public static int solve(){
        // 알파벳별로 count에 의한 내림차순 정렬
        Element[] arr = new Element[len];
        for(int i =0 ;i <len;i++){
            arr[i] = new Element(i,alphaCnt[i]);
        }
        Arrays.sort(arr,(o1,o2)->o2.val-o1.val);
        // 알파벳에게 값을 할당한다
        int number = 9;
        for(int i =0 ;i <len;i++){
            if(arr[i].val != 0) alphaValue[arr[i].ch] = number--;
        }
        // 최종값 구하기
        int sum = 0;
        for(int alpha = 0 ; alpha<len;alpha++){
            sum += alphaCnt[alpha]*alphaValue[alpha];
        }
        return sum;
    }

    public static void main(String[] args) throws IOException{
        setting();
        System.out.println(solve());
    }
}