// 正の整数のリストを与えられたとき、
// 数を並び替えて可能な最大数を返す関数を記述せよ。
// 例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。
import java.util.*;
public class Main {
public static void main(String[] args){
test(Arrays.asList(50, 2, 1, 9));
test(Arrays.asList(991, 9, 92));
test(Arrays.asList(112, 113, 18, 12, 1));
}
// 試運転
public static void test(List<Integer> list){
p(list + " => " + solve(list));
}
// 解く
public static String solve(List<Integer> list){
Map<Integer, Integer> map = new HashMap<>();
int len = list.size();
for(int i=0; i<len; i++){
map.put(i, list.get(i));
}
String result = "";
// mapを減らす
while(0 < map.size()){
int key = getStrMaxKeyOfMap(map);
result += map.get(key);
map.remove(key);
}
return result;
}
// -32=>2, 32=>2, 0=>1, 334=>3
public static int getKeta(int n){
if(n<0){
n *= -1;
}
return ("" + n).length();
}
// 43=>3, 3=>3, -2=>-2, -21=>-1
public static int removeMaxDigit(int n){
if(-9 <= n && n <= 9){
return n;
}
int oneZero = (int)Math.pow(10, getKeta(n)-1);
return n % oneZero;
}
// 99と992と3なら99を返却するbyMap
public static int getStrMaxKeyOfMap(Map<Integer, Integer> map){
// エリートを抽出。[50, 2, 1, 9, 91]なら[9, 91]
Map<Integer, Integer> eliteMap = generateEliteMap(map);
if(eliteMap.size() == 1){
/* エリートが1つである */
// そいつを返却
for(int key : eliteMap.keySet()){
return key;
}
}
/* エリートが複数である */
if(isAllSameValue(eliteMap)){
/* すべて同じ数字である */
// そいつを返却
for(int key : eliteMap.keySet()){
return key;
}
}
/* エリートが複数、かつ1桁の値はない */
// 全ての要素の最大桁の数字を落として、桁を下げる
Map<Integer, Integer> eliteMap2 = new HashMap<>();
for(int key : eliteMap.keySet()){
int value = eliteMap.get(key);
eliteMap2.put(key, removeMaxDigit(value));
}
// 再帰呼出し
return getStrMaxKeyOfMap(eliteMap2);
}
// 全て同じ数字ならtrue
public static boolean isAllSameValue(Map<Integer, Integer> map) {
// 代表値を決定する
int typicalValue = -1;
for(int key : map.keySet()){
typicalValue = map.get(key);
break;
}
// 違う値があるかチェック
for(int key : map.keySet()){
int value = map.get(key);
if(value != typicalValue){
/* 違う値があった */
return false;
}
}
/* 違う値がなかった */
return true;
}
public static List<Integer> generateListFromMap(Map<Integer, Integer> map){
List<Integer> list = new ArrayList<>();
for(int key : map.keySet()){
int value = map.get(key);
list.add(value);
}
return list;
}
// 33, 33, 44, 44 なら44, 44を返却map
public static Map<Integer, Integer> generateEliteMap(Map<Integer, Integer> map){
// mapをlistにする
List<Integer> list = generateListFromMap(map);
// maxDigitNum取得。345=>3
int maxDigitNumOfList = getMaxDigitNumOfList(list);
// エリートマップを作成する
Map<Integer, Integer> eliteMap = new HashMap<>();
for(int key : map.keySet()){
int value = map.get(key);
if(getMaxDigitNum(value) == maxDigitNumOfList){
eliteMap.put(key, value);
}
}
return eliteMap;
}
// 33, 33, 44, 44 なら44, 44を返却
public static List<Integer> generateEliteList(List<Integer> list){
int maxDigitNumOfList = getMaxDigitNumOfList(list);
List<Integer> eliteList = new ArrayList<>();
for(int n : list){
if(getMaxDigitNum(n) == maxDigitNumOfList){
eliteList.add(n);
}
}
return eliteList;
}
// 33, 33, 44, 44 なら4を返却
public static int getMaxDigitNumOfList(List<Integer> list){
int max = getMaxDigitNum(list.get(0));
for(int n : list){
n = getMaxDigitNum(n);
if(max < n){
max = n;
}
}
return max;
}
// 値を指定して1要素削除する
public static void removeOnceByValue(List<Integer> list, int value){
int len = list.size();
for(int i=0; i<len; i++){
if(list.get(i) == value){
list.remove(i);
return;
}
}
}
// クローンを作成して返す
public static List<Integer> generateClone(List<Integer> list){
List<Integer> clone = new ArrayList<>();
for(int n : list){
clone.add(n);
}
return clone;
}
// 一番左の数字を返す
public static int getMaxDigitNum(int n){
if(n < 0){
n *= -1;
}
String[] sa = ("" + n).split("");
return Integer.parseInt(sa[0]);
}
public static void dispList(List<Integer> a){
for(int n : a){
p(n);
}
}
public static void p(Object o){
System.out.println(o);
}
}
