「ソフトウェアエンジニアならば1時間以内に解けなければいけない5つの問題」
の
第4問
正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。
を解いた。難しすぎ。Javaの正攻法で解いた。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 |
// 正の整数のリストを与えられたとき、 // 数を並び替えて可能な最大数を返す関数を記述せよ。 // 例えば、[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); } } |
|
1 2 3 |
[50, 2, 1, 9] => 95021 [991, 9, 92] => 999192 [112, 113, 18, 12, 1] => 18121131121 |
