[JAVA/1399번] 단어 수학

문제

입력 및 출력

풀이

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

class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N
        int N = Integer.parseInt(br.readLine());

        // 알파벳을 입력받을 배열 words
        String[] words = new String[N];
        for (int i = 0; i < N; i++) {
            words[i] = br.readLine();
        }

        // A-Z사이의 알파벳 26개
        int[] alphabet = new int[26];

        for (int i = 0; i < N; i++) {
            // 자리수 계산
            int temp = (int) Math.pow(10, words[i].length() - 1);

            // i번째 단어의 길이만큼 반복문 수행
            for (int j = 0; j < words[i].length(); j++) {
                // 해당 알파벳의 자리에 자릿수를 더해준다.(65는 A의 아스키코드)
                alphabet[(int) words[i].charAt(j) - 65] += temp;

                // 한 자리수씩 줄어든다.
                temp = temp / 10;
            }
        }

        // 정렬 메소드 사용
        Arrays.sort(alphabet);

        // 0~9 중 가장 큰 수
        int number = 9;

        // 결과 값을 담을 변수
        int result = 0;

        // 위에서 오름차순으로 정렬했기 때문에 역순으로 반복문 수행
        for (int i = alphabet.length - 1; i >= 0; i--) {
            // 이 이후의 반복문은 다 0이기 때문에 break
            if (alphabet[i] == 0) {
                break;
            }

            result += alphabet[i] * number;
            number--;
        }

        // 결과 값 출력
        System.out.println(result);
    }
}

결과 및 해결방법

[결과]

[정리]

실패코드

// A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7
import java.io.*;
import java.util.*;

class Main {
    public static int MAX = Integer.MIN_VALUE;
    public static int N;

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 단어의 개수 N(1 <= N <= 10)
        N = Integer.parseInt(br.readLine());

        String[] word = new String[N];
        for (int i = 0; i < N; i++) {
            word[i] = br.readLine();
        }

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (word[i].length() < word[j].length()) {
                    String temp = word[i];
                    word[i] = word[j];
                    word[j] = temp;
                }
            }
        }

        // 키와 값을 갖는 자료구조 선언
        Map < Character, Integer > map = new HashMap < > ();

        // 스택 자료구조 선언
        Stack < Integer > stack = new Stack < > ();

        // 0 ~ 9 사이의 가장 큰 수
        int initNum = 9;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < word[i].length(); j++) {
                if (map.get(word[i].charAt(j)) == null) {
                    map.put(word[i].charAt(j), initNum);
                    initNum--;
                }
            }

            String result = "";
            for (int j = 0; j < word[i].length(); j++) {
                int alphabet = map.get(word[i].charAt(j));
                result += String.valueOf(alphabet);
            }
            System.out.println(result);
            stack.push(Integer.parseInt(result));
        }

        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        // 결과 값 출력
        System.out.println(result);
    }
}

해결방법
처음 문제를 보았을 때, 해결하려고 했던 방법은 입력받은 두 단어의 길이를 비교하여 길이가 긴 순으로 정렬을 수행하고 맵 자료구조를 통해 알파벳의 앞에서 부터 차례대로 입력시켜주는 방법으로 진행했다.

하지만, 위 방법으로 수행했을 경우 동일한 동일한 자리수에 대한 처리가 어려웠고 문제를 다시 생각하게 되었다.

이 문제는 최댓값을 구하는 문제로 자릿수에 따라 가장 큰 숫자를 곱해주면 해결할 수 있겠다 생각이 들었다.
문제의 2번 예시는 GCF와 ACDEB를 입력받는다. GCF는 3자리 수로 100부터 시작하고, ACDEB는 5자리 수로 10000부터 시작하는 것을 알 수 있다. 따라서 10에 알파벳의 길이 - 1을 한 값을 제곱하여 자릿수를 알 수 있었고 알파벳의 길이만큼 반복문을 수행하며 해당 알파벳 자리에 자릿수를 넣어주었다.

다음으로 가장 큰 자릿수(10000)와 큰 수(9)를 곱해야하기 때문에 알파벳 배열을 오름차순으로 정렬하고, 거꾸로 반복문을 수행하였다. 자릿수의 크기별로 정렬이 되었기 때문에 알파벳 배열의 i번째 원소가 0이 아닐경우까지 수를 감소하며 곱을 수행하고 결과값에 더했다.