[백준 Gold 4] 1339 단어 수학 - Java

문제링크 : https://www.acmicpc.net/problem/1339

1339번: 단어 수학

 

접근 과정 : 

• 사용되는 알파벳의 개수를 확인하여 가장 많이 사용되는 것부터 9를 할당시킨다.
• 알파벳의 개수를 체크할 때, 자릿수에 대한 가중치를 부여 (10^자릿수)
• 처음에는 HashMap을 이용해서 체크했는데.. 
• 다 작성하고 보니, 그냥 int배열하나로도 충분할 것 같아서 다시 작성.

 

소스 코드 및 결과 :

package BOJ;

/* 
    단어 수학
    
    HashMap 이용

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

public class BOJ1339_copy {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        HashMap<Character, Integer> alphabet = new HashMap<>();

        int sum = 0;

        while (N-- > 0) {
            String s = br.readLine();

            for (int i = 0; i < s.length(); i++) {
                alphabet.put(s.charAt(i),
                        alphabet.getOrDefault(s.charAt(i), 0) + (int) Math.pow(10, s.length() - i - 1));
            }
        }

        List<Character> list = new ArrayList<>(alphabet.keySet());
        Collections.sort(list, (a, b) -> {
            return alphabet.get(b) - alphabet.get(a);
        });

        int num = 9;
        for (char a : list) {
            sum += (num * alphabet.get(a));
            num--;

        }

        System.out.println(sum);

    }
}

 

package BOJ;

/* 
    단어 수학
	
    int 배열 이용
*/
import java.io.*;
import java.util.*;

public class BOJ1339 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] alphabet = new int[26];

        while (N-- > 0) {
            String s = br.readLine();

            for (int i = 0; i < s.length(); i++) {
                alphabet[s.charAt(i) - 'A'] += (int) Math.pow(10, s.length() - i - 1);
            }
        }

        Arrays.sort(alphabet);

        int sum = 0;
        int num = 9;
        for (int i = 25; i >= 0; i--) {
            if (alphabet[i] == 0) {
                continue;
            }

            sum += (alphabet[i] * num);
            num--;
        }

        System.out.println(sum);

    }
}

 

P.S 

어떤 자료구조를 사용하냐에 따라서 시간비용의 차이가 발생하였다.

(Java11의 경우, 내부 로직의 성능이 좋아졌는지 큰 차이를 보이지 않았지만.)

 

특히, 알파벳의 개수가 26개로 적어서 int배열을 전부 순회해도 많은 시간이 필요하지 않아서 배열이 더 좋은듯 싶다.