AnagramGroup.java

package problem.boj;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

/**
 * Created by Jinseoung on 2017-01-01.
 */
public class AnagramGroup {
    static Scanner sc = new Scanner(ClassLoader.getSystemResourceAsStream("problem/boj/AnagramGroup.testcase"));

    static Word[] redixSort (Word[] words) {
        int maxLength = getMaxLength(words);

        for(int index = 1; index <= maxLength; index++) {
            Word[] newWords = new Word[words.length];
            int[] counts = new int[27];

            for(int i = 0; i < words.length; i++) {
                Word word = words[i];
                counts[index > word.length ? 26 : word.counts[word.length-index]-'a']++;
            }

            for(int i = 1; i < 27; i++) counts[i] += counts[i-1];

            for(int i = words.length-1; i >= 0; i--) {
                Word word = words[i];
                newWords[--counts[index > word.length ? 26 : word.counts[word.length-index]-'a']] = word;
            }

            words = newWords;
        }

        return words;
    }

    static int getMaxLength (Word[] strings) {
        int result = 0;

        for(int i = 0; i < strings.length; i++){
            if(result < strings[i].length) result = strings[i].length;
        }

        return result;
    }

    static class Word {
        String word;
        char[] counts;
        int length = 0;

        public Word(String word) {
            this.word = word;
            this.length = word.length();
            this.counts = new char[word.length()];

            int[] counts = new int[26];
            int countsPosition = 0;

            for(int i = 0 ; i < word.length(); i++) {
                counts[word.charAt(i)-'a']++;
            }

            // counting sort
            for(int i = 0; i < 26; i++) {
                for(int j = 0; j < counts[i]; j++) {
                    this.counts[countsPosition++] = (char) (i + 'a');
                }
            }
        }
    }

    static class Anagram {
        int count=1;
        String word;
        ArrayList<String> words = new ArrayList<>();
        String counts;

        public Anagram(String word, String counts) {
            this.word = word;
            this.words.add(word);
            this.counts = counts;
        }

        public boolean equals(Anagram obj) {
            return counts.equals(obj.counts);
        }

        public void merge(Anagram anagram) {
            if(this.word.compareTo(anagram.word) > 0) {
                this.word = anagram.word;
            }
            words.add(anagram.word);
            this.count++;
        }

        public String getWords () {
            StringBuilder stringBuilder = new StringBuilder();

            words.sort(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.compareTo(o2);
                }
            });

            String previousWord = null;
            for(String word : words) {
                if(!word.equals(previousWord)) {
                    stringBuilder.append(word + " ");
                    previousWord = word;
                }
            }

            return stringBuilder.toString();
        }

        public String getFormat() {
            return String.format("Group of size %d: %s.", count, getWords());
        }
    }

    public static void main(String[] args) {
        ArrayList<Word> wordArrayList = new ArrayList<>();

        while(sc.hasNext()){
            wordArrayList.add(new Word(sc.next()));
        }

        Word[] words = redixSort(wordArrayList.toArray(new Word[]{}));

        ArrayList<Anagram> anagrams = new ArrayList<>();

        Anagram anagram = new Anagram(words[0].word, new String(words[0].counts));
        for(int i = 1; i < words.length; i++){
            Anagram newerAnagram = new Anagram(words[i].word, new String(words[i].counts));
            if(anagram.equals(newerAnagram)) {
                anagram.merge(newerAnagram);
            } else {
                anagrams.add(anagram);
                anagram = newerAnagram;
            }
        }
        anagrams.add(anagram);

        Collections.sort(anagrams, (o1, o2) -> {
            if(o1.count == o2.count) {
                return o1.word.compareTo(o2.word);
            }

            return o2.count - o1.count;
        });

        for(int i = 0 ; i < 5; i++) {
            System.out.println(anagrams.get(i).getFormat());
        }
    }
}