[백준:JAVA] 단어수학

목차

문제링크 :

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

1339번: 단어 수학

문제 :

# 1339_단어수학

***

## 문제 설명
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 
이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 
같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 
두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

## 입력
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 
둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 
모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 
서로 다른 문자는 서로 다른 숫자를 나타낸다.

## 출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

### 예제입력1
```
2 
AAA 
AAA
```
### 예제 출력 1 
1998


### 예제 입력 2 
```
2
GCF
ACDEB
```

### 예제 출력 2 
99437


### 예제 입력 3 
```
10
A
B
C
D
E
F
G
H
I
J
```
### 예제 출력 3 
45

풀이과정

🔐문제풀이 로직

1. 입력받은 문자열의 알파벳을 키로 가지고 있는 딕셔너리 생성 → value값으로 자릿수 저장키값이 있다면 자릿값 누적, 없다면 자릿값 더하기
2. containsKey()[# map.containsKey(key) : map에 key존재 유무를 T/F로 반환 ]: hashmap이 키 값을 가지고 있는지 확인
3. map 요소 정렬 : value 기준

List<Map.Entry<Character, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });

 4. 딕셔너리에 저장된 value가 가장 큰순서대로, 9~0 부여.

 5. 입력받은 문자열을 딕셔너리에 자장된 값과 1:1 매치.

 

내 풀이

초안

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.List;
import java.util.LinkedList;
import java.util.Comparator;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Character,Integer> map = new HashMap<>();
        int n = Integer.parseInt(br.readLine());
        String[] input_arr = new String[n];

        for(int i=0; i<n; i++)
        {
            String input = br.readLine();
            for(int j=input.length()-1; j>=0; j--) {
                char key = input.charAt(input.length()-1-j);
                for(int j=input.length()-1; j>=0; j--) {
                    char key = input.charAt(input.length() - 1 - j);
                    if(!map.containsKey(key)) // hashmap value 누적 업데이트 
                        map.put(key, (int)Math.pow(10,j));
                    else
                        map.put(key, map.get(key) + (int)Math.pow(10,j));
		         }
            input_arr[i] = input;
        }

        // hashmap value기준으로 요소 정렬
        List<Map.Entry<Character, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });

        //map 요소 중, 값이 큰 순서대로 9~ 값 부여하기
        int idx = 9;
        for(Map.Entry<Character, Integer> entry : entryList){
            map.put(entry.getKey(), idx) ;// 덮어쓰기
            idx --;
        }

        int answer = 0 ;
        // 값 대체
        for(String str:input_arr)
            for (int j=str.length()-1; j>=0; j--)
                answer += map.get(str.charAt(str.length()-1-j))   *Math.pow(10,j) ;
        System.out.println(answer);

    }
}

제출하고보니, 내 코드가 속도는 빨랐지만, 다른사람에 비해 길이가 많이 길었다.

찾아보니 함수로 대체할 수 있는데 코드로 작성한 부분도 꽤 있었기 때문인 것 같다.

변경사항 1.continsKey() -> map.get() + 삼항연산자 사용 

// 변경전 코드 
for(int j=input.length()-1; j>=0; j--) {
    char key = input.charAt(input.length() - 1 - j);
    map.put( key, (map.get(key)!=null?map.get(key):0 ) +(int)Math.pow(10,j) );

    if(!map.containsKey(key))
        map.put(key, (int)Math.pow(10,j));
    else
        map.put(key, map.get(key) + (int)Math.pow(10,j));
    
}

//변경 후 코드 
for(int j=input.length()-1; j>=0; j--) {
    char key = input.charAt(input.length() - 1 - j);
    map.put( key, (map.get(key)!=null?map.get(key):0 ) +(int)Math.pow(10,j) );
}

 

 

변경사항2. 요소를 정렬 후 9~값 부여 후, 대치 -> 정렬 후, 9~부여와 동시에 대치 

//변경 전 
//map 요소 중, 값이 큰 순서대로 9~ 값 부여하기
int idx = 9;
for(Map.Entry<Character, Integer> entry : entryList){
    map.put(entry.getKey(), idx) ;// 덮어쓰기
    idx --;
}

int answer = 0 ;
// 값 대체
for(String str:input_arr)
    for (int j=str.length()-1; j>=0; j--)
        answer += map.get(str.charAt(str.length()-1-j))   *Math.pow(10,j) ;
System.out.println(answer);

//변경 후
int answer = 0;
int idx = 9;
for (Map.Entry<Character, Integer> entry : entryList) {
    answer += map.get(entry.getKey()) * idx;
    idx--;
}
System.out.println(answer);

딕셔너리에 있는 값과 1:1로 매치시켜 더해야 하기 떄문에 hashMap활용하면 간편할 것이라 생각했는데, 속도는 빠르긴 하지만 value를 기준으로 정렬하기 너무 어려웠다.

반면에, 다른 분들처럼 기본 배열을 활용하여 풀면, 속도는 haspMap을 활용하는것과 비슷하지만 코드 짜기에 훨씬 쉽고 가독성도 좋은 것 같다.

 

최종

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.List;
import java.util.LinkedList;
import java.util.Comparator;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Character,Integer> map = new HashMap<>();
        int n = Integer.parseInt(br.readLine());
        String[] input_arr = new String[n];

        for(int i=0; i<n; i++)
        {
            String input = br.readLine();
            for(int j=input.length()-1; j>=0; j--) {
                char key = input.charAt(input.length()-1-j);
                for(int j=input.length()-1; j>=0; j--) {
                    char key = input.charAt(input.length() - 1 - j);
                    map.put(key, (int)Math.pow(10,j) + (map.get(key)!=null?map.get(key):0 ));
		    }
            input_arr[i] = input;
        }

        // hashmap - value기준으로 요소 정렬
        List<Map.Entry<Character, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });

        int answer = 0;
        int idx = 9;
        for (Map.Entry<Character, Integer> entry : entryList) {
            answer += map.get(entry.getKey()) * idx;
            idx--;
        }
        System.out.println(answer);

    }
}

 

다른사람 풀이 1

string배열과 int배열을 동시 생성해서

string배열에는 문자열을, int배열에는 알파벳 아스키코드-65에 해당하는 자리에 자릿수를 저장했다

ex. a = alpha_vale[0] , b= alpha_vale[1]

-- 이하 동일 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int N = Integer.parseInt(br.readLine());
        String[] alphabet_lst = new String[N];
        int[] alpha_value = new int[26];
        for (int i = 0; i < N; i++) {
            alphabet_lst[i] = br.readLine();
        }
       
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < alphabet_lst[i].length(); j++) {
                char word = alphabet_lst[i].charAt(j);
                alpha_value[word-65] += (int)Math.pow(10, alphabet_lst[i].length()-j-1);
            }
        }
        Arrays.sort(alpha_value);
       
        int num = 9;
        int sum = 0;
        int turn = 25;
       
        while (turn != 0) {
            sum += alpha_value[turn] * num;
            --num;
            --turn;
        }
       
        System.out.println(sum);
    }
}
 

 

다른사람 풀이 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] alphabet = new int[27];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < str.length(); j++) {
                alphabet[str.charAt(j) - 65] += Math.pow(10, str.length() - 1 - j);
            }
        }
        Arrays.sort(alphabet);
        int num = 9;
        int ans = 0;
        for (int i = 26; i >= 0; i--) {
            if (alphabet[i] != 0) {
                ans += num * alphabet[i];
                num--;
            }
        }
        System.out.println(ans);
    }
}

 

𝚂𝚘𝚞𝚛𝚌𝚎 𝚌𝚘𝚍𝚎

https://github.com/xnsl291/Algorithms-study/tree/main/BaekJoon/java/Gold4/1339_%EB%8B%A8%EC%96%B4%EC%88%98%ED%95%99

GitHub - xnsl291/Algorithms-study: 알고리즘 공부하며 풀었던 코드들을 업로드 하는 곳