[yukicoder] No.628 Tagの勢い - ヤマカサのプログラミング勉強日記

アルゴリズムの問題を解く

yukicoderのレベル1.5の問題を解いていきたいと思います。

方針

入力された値を格納にするにあたり、動的な配列を使いたかったので、HashMapを使いました。数値のソートと文字列の辞書順に整列させるために、挿入ソートを使いました。

コード

import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;

public class Tag {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int []No = new int[N];
        int []S = new int[N];

        //String str[][] = new String[N][];
        HashMap<Integer, HashMap<Integer, String>> strD2
                = new HashMap<Integer, HashMap<Integer, String>>();
        for(int i = 0; i < N; i++) {
            No[i] =  scanner.nextInt();
            int M = scanner.nextInt();
            S[i] = scanner.nextInt();
            HashMap<Integer, String> strD1 = new HashMap<Integer, String>();
            for(int j = 0; j < M; j++) {
                String s = scanner.next();
                strD1.put(j, s);

            }
            strD2.put(i, strD1);
        }
        scanner.close();


        HashMap<String, Integer> pointHM = new HashMap<String,Integer>();
        pointHM.put(strD2.get(0).get(0), 0);
        int k;
        String key;
        for(int i = 0; i < N; i++) {
            k = strD2.get(i).size();
            for(int j = 0; j < k; j++) {
                key = strD2.get(i).get(j);
                if(pointHM.containsKey(key)) {
                    int s = pointHM.get(key);
                    pointHM.put(key, s + S[i]);
                }else {
                    pointHM.put(key, S[i]);
                }
            }
        }
        Set<String> pointSet = pointHM.keySet();
        String s = pointSet.toString().substring(1, pointSet.toString().length() - 1);

        String[] arrayKey = s.split("[\\s]*,[\\s]*");

        int keyLen = arrayKey.length;
        int[]point = new int[keyLen];
        for(int i = 0; i < keyLen; i++) {
            point[i] = pointHM.get(arrayKey[i]);
        }


        int v;
        int j;
        String temp;
        for(int i = 1; i < keyLen; i++) {
            v = point[i];
            temp = arrayKey[i];
            j = i - 1;
            while( j >= 0 && arrayKey[j].compareTo(temp) > 0) {
                arrayKey[j + 1] = arrayKey[j];
                point[j + 1] = point[j];
                j--;
            }
            arrayKey[j + 1] = temp;
            point[j + 1] = v;
        }

        for(int i = 1; i < keyLen; i++) {
            v = point[i];
            temp = arrayKey[i];
            j = i - 1;
            while( j >= 0 && point[j] < v) {
                arrayKey[j + 1] = arrayKey[j];
                point[j + 1] = point[j];
                j--;
            }
            arrayKey[j + 1] = temp;
            point[j + 1] = v;
        }
        if(keyLen > 10) {
            for(int i = 0; i < 10; i++) {
                System.out.println(arrayKey[i] + " " + point[i]);
            }
        }else {
            for(int i = 0; i < keyLen; i++) {
                System.out.println(arrayKey[i] + " " + point[i]);
            }
        }

    }
}