「第9回 オフラインリアルタイムどう書く」参考問題: へなちょこ解答（Java）

どう書く

数字を作ったぞ！！！

4/6のどう書くにはまだ空きがあるようです。お暇な方は参加してみてはいかがでしょうか。きっと楽しいですよ。

時間内に解けなくても発表しなくちゃいけませんけど…ぐぎぎ（何度もやっている）

自分の解答

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 問題: http://nabetani.sakura.ne.jp/hena/ord9nummake/
 */
public class NumberMake {

	public String solve(String input) {
		int order = Integer.valueOf(input.split(":")[0]);
		String cards = input.split(":")[1];
		Set<String> cardsSet = getCardsSet(cards);

		Set<String> cardSet = new HashSet<>();
		for (String each : cardsSet) {
			Set<String> tmpSet = makeNum("", each);
			cardSet.addAll(tmpSet);
		}
		cardSet = checkZero(cards, cardSet);

		List<String> cardList = new ArrayList<>(cardSet);
		Collections.sort(cardList);
		if (cardList.size() < order) {
			return "-";
		}
		return cardList.get(order - 1);
	}

	protected Set<String> getCardsSet(final String cards) {
		Set<String> result = new HashSet<>();
		result.add(cards);
		String tmp = cards;
		for (int i = 0; i < getSixNum(cards); i++) {
			tmp = tmp.replaceFirst("6", "9");
			result.add(tmp);
		}
		return result;
	}

	protected int getSixNum(String cards) {
		int result = 0;
		for (int i = 0; i < cards.length(); i++) {
			if (cards.charAt(i) == '6') {
				result++;
			}
		}
		return result;
	}

	protected Set<String> makeNum(final String card, String cards) {
		Set<String> result = new HashSet<>();

		for (int i = 0; i < cards.length(); i++) {
			String tmpCard = card;
			tmpCard += cards.charAt(i);

			String next = "";
			if (0 < i) {
				next += cards.substring(0, i);
			}
			if (i < cards.length() - 1) {
				next += cards.substring(i + 1);
			}
			// System.out.println("card: " + tmpCard + ", next: " + next);
			if (tmpCard.length() < 4) {
				Set<String> tmp = makeNum(tmpCard, next);
				result.addAll(tmp);
			} else {
				result.add(tmpCard);
			}
		}
		return result;
	}

	protected Set<String> checkZero(String cards, Set<String> cardList) {
		Set<String> result = new HashSet<>();
		for (String string : cardList) {
			if (string.startsWith("0") == false) {
				result.add(string);
			}
		}
		return result;
	}
}

考え方の覚書き

getCardsSetメソッド

「6」のカードが「9」としても使われる可能性があることを考慮する必要があります。「9」として使われたカードが、同時に「6」として使われることはありません。

getCardsSetメソッドでは、入力に「6」が1〜n枚あるときに、すべて「6」とみなす入力、1枚の「6」が「9」として扱われる入力、...、n枚の「6」が「9」として扱われる入力、といったSetを作って返します。

makeNumメソッド

n枚から4枚の組合せを作るためのメソッドです。

このあたりのコードをじっと見て、参考にしたつもり。

checkZeroメソッド

最上位ケタが「0」の解答が含まれている場合、排除します。

引っ掛かったところ

最初はListを使っていましたが、重複解答を排除するためにSetに変えました。

また、「6」のカードがあるときに、結果セットの「6」を一律「9」に変える処理を書いていました。これは、例題のような入力だとテストが通りますが、「6」が2枚以上ある入力だとダメです。一部の「6」を「9」として使わない場合があるからです。愚かすぎた。

ひとととおりの実装に1時間半弱、テストを通すのに15分ほどかかりました。