雀魂という麻将ゲームに興味を持ったユーザーが、複雑なルールを簡略化して新しい麻将を作りました。この新しいルールでは、1から9までの数値の牌を使用し、各数値の牌は4枚ずつ存在します。手札は14枚で構成され、和了の条件は以下の通りです。
- 14枚の牌の中に2枚同じ数値の牌（雀頭）が含まれていること。
- 雀頭を除いた残りの12枚の牌が、4つの順子または刻子で構成されていること。順子とは連続する3つの数値の組み合わせ（例：234, 567）であり、刻子とは同じ数値の3つの組み合わせ（例：111, 777）です。
ユーザーはすでに13枚の牌を持っています。残りの23枚の中から1枚を引いて和了となる場合の数値を求めることになりました。
入力
入力は1行で、13個の数字がスペース区切りで与えられます。各数字は1から9の間で、同じ数字は最大4回しか出現しません。
出力
出力は1行で、和了となる可能性のある数字を昇順でスペース区切りで出力します。複数の数字が該当する場合はそれらを全て出力します。どの数字でも和了にならない場合は0を出力します。
例
入力例1:
1 1 1 2 2 2 5 5 5 6 6 6 9
出力例1:
9
入力例2:
1 1 1 1 2 2 3 3 5 6 7 8 9
出力例2:
4 7
入力例3:
1 1 1 2 2 2 3 3 3 5 7 7 9
出力例3:
0
解法
問題を解決するために、再帰を使って全通りの組み合わせを試す方法を採用しました。雀頭、刻子、順子のいずれかとして使用可能な数字をリストに入れて、それぞれのケースについて再帰的に調査を行います。
import java.util.*;
public class MahjongSolver {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<Integer> hand = new ArrayList<>();
for (int i = 0; i < 13; i++) {
hand.add(scanner.nextInt());
}
StringBuilder result = new StringBuilder();
for (int tile = 1; tile <= 9; tile++) {
List<Integer> potentialHand = new ArrayList<>(hand);
potentialHand.add(tile);
Collections.sort(potentialHand);
if (canWin(potentialHand, false)) {
result.append(tile).append(" ");
}
}
if (result.length() == 0) {
System.out.println("0");
} else {
System.out.println(result.toString().trim());
}
}
private static boolean canWin(List<Integer> tiles, boolean hasPair) {
if (tiles.isEmpty()) {
return true;
}
if (!hasPair && isPair(tiles.get(0), tiles.get(1))) {
List<Integer> remainingTiles = removeTiles(tiles, 0, 1);
if (canWin(remainingTiles, true)) {
return true;
}
}
if (tiles.size() >= 3) {
if (isTriplet(tiles.get(0), tiles.get(1), tiles.get(2))) {
List<Integer> remainingTiles = removeTiles(tiles, 0, 1, 2);
if (canWin(remainingTiles, hasPair)) {
return true;
}
}
if (isSequence(tiles.get(0), tiles.get(1), tiles.get(2))) {
List<Integer> remainingTiles = removeTiles(tiles, 0, 1, 2);
if (canWin(remainingTiles, hasPair)) {
return true;
}
}
}
return false;
}
private static boolean isPair(int a, int b) {
return a == b;
}
private static boolean isTriplet(int a, int b, int c) {
return a == b && b == c;
}
private static boolean isSequence(int a, int b, int c) {
return a + 1 == b && b + 1 == c;
}
private static List<Integer> removeTiles(List<Integer> tiles, int... indices) {
List<Integer> remainingTiles = new ArrayList<>(tiles);
Arrays.sort(indices);
for (int i = indices.length - 1; i >= 0; i--) {
remainingTiles.remove(indices[i]);
}
return remainingTiles;
}
}