문제 1339번

소스코드

import java.io.*;
import java.util.*;
public class boj1339 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] arr = new String[N];
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            StringBuilder sb = new StringBuilder(input);
            arr[i] = sb.reverse().toString();
        }
        Arrays.sort(arr, (s1,s2) -> s2.length() - s1.length());
        Map<Character, Integer> alphabet = new HashMap<>();
        int high = arr[0].length()-1;
        for (int i = high; i >= 0; i--) {
            for (int j = 0; j < N; j++) {
                if(i>= arr[j].length()){
                    break;
                }
                char a = arr[j].charAt(i);
                if(!alphabet.containsKey(a)){
                    alphabet.put(a, (int)Math.pow(10,i));
                }else{
                    alphabet.put(a, alphabet.get(a) + (int)Math.pow(10,i));
                }
            }
        }
        List<Integer> list = new ArrayList<>();
        for(Character c : alphabet.keySet()){
            list.add(alphabet.get(c));
        }
        Collections.sort(list, (a,b) -> b-a);
        int num = 9; int ans = 0;
        for (int i = 0; i < list.size(); i++) {
            ans += list.get(i)*num--;
        }
        System.out.println(ans);
    }
}

풀이 접근

• 문제 풀이 방식으로 조합을 통한 완전탐색으로 값을 도출하는 방식과, 알파벳의 해당 자리에 대한 값으로 우선순위를 통해 값을 출력하는 방식을 생각했다.
• 조합의 경우가 다양해질 것 같아서 시간을 줄이기 위해 우선순위를 통한 출력 방식으로 접근하게 되었다.
• 입력받은 값을 reverse시켜 저장하고, String[] 배열에 넣을 것이다.
  String배열은 이 다음에 예외처리를 쉽게 구현하기 위해 내림차순으로 정렬해 준다.
  2중 반복문을 통해 해당 자릿값에 따른 우선순위 값을 hashmap을 통해 넣어준다. ex) AAB의 경우 (A,100+10) (B,1)
  우선순위가 높은 문자 부터 받기 위해 내림차순으로 정렬하고, 앞 인덱스 부터
  9 8 7 6 .... 식으로 곱한 값을 다 더해 출력한다.

문제 핵심

• 그리디 알고리즘의 구현