[백준] 1339 단어 수학 - 자바

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

1339번: 단어 수학

문제 풀이

몇 십분 동안 고민했지만 해결법이 안 떠올라 구글링을 통해 해법을 찾고 구현을 시도했다. 단순히 따라치는 것이 아니라 설계를 이해하고 직접 쳐보는 것이 중요한 것 같다.

 

처음 내가 생각한 접근법은 비슷했다.

1. 각 알파벳이 높은 자리수에 위치
2. 같은 자리수라면 더 많이 등장한 횟수

위 접근법을 구현하고자 자리수와 등장횟수를 관리하기에는 너무 어려웠다. 구글링해서 얻은 해법은 각 자리수에 대해 가치를 부가하는 것이다. A가 천의 자리수에서 1번 등장했다면 1000A. B가 천의 자리수에 1번, 십의 자리수에 1번 등장했다면 1010B라는 가치를 얻는다. 따라서 같은 자리수의 A와 B가 있더라도 B가 9의 값을 얻도록 구현할 수 있다.

 

구현

전체 알파벳이 26개로 각 알파벳을 구분하기 위해 26개의 배열을 생성해준다. int가 아닌 Integer를 사용한 이유는 마지막에 내림차순을 해주기 위함이다. 또한, new int[]는 자동으로 0이 초기화 되지만 new Integer[]는 null이 들어가기 때문에 알파벳의 가치를 더해주기 위해 0으로 미리 초기화해야 한다.

Integer[] alphabets = new Integer[26];
Arrays.fill(alphabets, 0);

 

A는 0번인덱스부터 시작하여 Z는 25번인덱스를 가지고 각 자리수의 가치를 얻어서 배열에 더해준다.

for (int i = 0; i < n; i++) {
    String str = br.readLine();
    int len = str.length();
    for (int j = 0; j < len; j++) {
        int pow = (int) Math.pow(10, len - j - 1);
        int idx = str.charAt(j) - 'A';
        alphabets[idx] += pow;
    }
}

 

마지막으로 가치가 큰순서가 먼저오도록 내림차순을 진행하고 앞 10개의 숫자에 대하여 값(9~0)을 곱한 값을 더해서 출력해준다.

알파벳이 총 10개만 나오기 때문에 내림차순 10개의 숫자에 대해서만 진행해도 무방하다.

Arrays.sort(alphabets, Comparator.reverseOrder());

int result = 0;
int order = 9;
for (int i = 0; i < 10; i++) {
    result += order * alphabets[i];
    order--;
}

 

코드

package 백준;

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

public class b1339 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Integer[] alphabets = new Integer[26];
        Arrays.fill(alphabets, 0);

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            int len = str.length();
            for (int j = 0; j < len; j++) {
                int pow = (int) Math.pow(10, len - j - 1);
                int idx = str.charAt(j) - 'A';
                alphabets[idx] += pow;
            }
        }

        Arrays.sort(alphabets, Comparator.reverseOrder());

        int result = 0;
        int order = 9;
        for (int i = 0; i < 10; i++) {
            result += order * alphabets[i];
            order--;
        }

        System.out.println(result);
    }
}