Baekjoon - 20529

문제

Solved.ac Class3++

1차시도

public class Main {
	private static String[] select = null;
	private static int minValue;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int size = Integer.parseInt(br.readLine());
		for (int i = 0; i < size; i++) {
			int caseSize = Integer.parseInt(br.readLine());
			String[] data = br.readLine().split(" ");
			loop(caseSize, data);
			sb.append(minValue).append("\n");
		}
		System.out.println(sb);
	}

	private static void loop(int caseSize, String[] data) {
		boolean[] isVisit = new boolean[caseSize];
		minValue = Integer.MAX_VALUE;
		for (int i = 0; i < caseSize - 2; i++) {
			select = new String[3];
			select[0] = data[i];
			isVisit[i] = true;
			solve(caseSize, data, isVisit, 1, i + 1);
			isVisit[i] = false;
		}
	}

	private static void solve(int caseSize, String[] data, boolean[] isVisited, int deep, int start) {
		if (deep == 3) {
			compare();
			return;
		}

		for (int i = start; i < caseSize; i++) {
			if (!isVisited[i]) {
				isVisited[i] = true;
				select[deep] = data[i];
				solve(caseSize, data, isVisited, deep + 1, i + 1);
				isVisited[i] = false;
			}
		}
	}

	private static void compare() {
		String[] splitData0 = select[0].split("");
		String[] splitData1 = select[1].split("");
		String[] splitData2 = select[2].split("");
		int count = 0;
		for (int i = 0; i < 4; i++) {
			if (!splitData0[i].equals(splitData1[i])) {
				count++;
			}
			if (!splitData0[i].equals(splitData2[i])) {
				count++;
			}
			if (!splitData1[i].equals(splitData2[i])) {
				count++;
			}
		}
		minValue = Math.min(minValue, count);
	}
}

시간 초과

2차시도

public class Main {
	private static String[] select = null;
	private static int minValue;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int size = Integer.parseInt(br.readLine());
		for (int i = 0; i < size; i++) {
			int caseSize = Integer.parseInt(br.readLine());
			String[] data = br.readLine().split(" ");
			if (caseSize > 32) {
				sb.append("0\n");
			} else {
				loop(caseSize, data);
				sb.append(minValue).append("\n");
			}
		}
		System.out.println(sb);
	}

	private static void loop(int caseSize, String[] data) {
		boolean[] isVisit = new boolean[caseSize];
		minValue = Integer.MAX_VALUE;
		for (int i = 0; i < caseSize - 2; i++) {
			select = new String[3];
			select[0] = data[i];
			isVisit[i] = true;
			solve(caseSize, data, isVisit, 1, i + 1);
			isVisit[i] = false;
		}
	}

	private static void solve(int caseSize, String[] data, boolean[] isVisited, int deep, int start) {
		if (deep == 3) {
			compare();
			return;
		}

		for (int i = start; i < caseSize; i++) {
			if (!isVisited[i]) {
				isVisited[i] = true;
				select[deep] = data[i];
				solve(caseSize, data, isVisited, deep + 1, i + 1);
				isVisited[i] = false;
			}
		}
	}

	private static void compare() {
		String[] splitData0 = select[0].split("");
		String[] splitData1 = select[1].split("");
		String[] splitData2 = select[2].split("");
		int count = 0;
		for (int i = 0; i < 4; i++) {
			if (!splitData0[i].equals(splitData1[i])) {
				count++;
			}
			if (!splitData0[i].equals(splitData2[i])) {
				count++;
			}
			if (!splitData1[i].equals(splitData2[i])) {
				count++;
			}
		}
		minValue = Math.min(minValue, count);
	}
}

MBTI의 총 개수는 16개이다. 이말은 17~32명까지는 최소 2명씩은 겹친다는 이야기이고
33+부터는 무조건 3명은 겹치는 사람이 생긴다. 따라서 33이상은 계산을 하지 않고 0을 넣어줬더니 시간초과가 나오지 않았다.

성공

코드 정리

public class Main {
	private static int minValue;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int size = Integer.parseInt(br.readLine());
		for (int i = 0; i < size; i++) {
			int caseSize = Integer.parseInt(br.readLine());
			String[] data = br.readLine().split(" ");
			if (caseSize > 32) {
				sb.append("0\n");
			} else {
				solve(caseSize, data);
				sb.append(minValue).append("\n");
			}
		}
		System.out.println(sb);
	}

	private static void solve(int caseSize, String[] data) {
		int count = 0;
		minValue = Integer.MAX_VALUE;
		for (int i = 0; i < caseSize - 2; i++) {
			String select1 = data[i];
			for (int j = i + 1; j < caseSize - 1; j++) {
				String select2 = data[j];
				for (int k = j + 1; k < caseSize; k++) {
					String select3 = data[k];

					String[] split1 = select1.split("");
					String[] split2 = select2.split("");
					String[] split3 = select3.split("");
					for (int l = 0; l < 4; l++) {
						if (!split1[l].equals(split2[l])) {
							count++;
						}
						if (!split1[l].equals(split3[l])) {
							count++;
						}
						if (!split2[l].equals(split3[l])) {
							count++;
						}
					}
					minValue = Math.min(minValue, count);
					count = 0;
				}
			}
		}
	}
}

ToKotlin

var minValue: Int = 0

fun main() {
    val sb = StringBuilder()
    val size = readln().toInt()
    for (i in 0..<size) {
        val caseSize = readln().toInt()
        val data = readln().split(" ")
        if (caseSize > 32) {
            sb.append("0\n")
        } else {
            solve(caseSize, data)
            sb.append(minValue).append("\n")
        }
    }
    println(sb)
}

fun solve(caseSize:Int, data: List<String>) {
    var count = 0
    minValue = Int.MAX_VALUE
    for (i in 0..<caseSize - 2) {
        val select1 = data[i]
        for (j in i + 1..<caseSize - 1) {
            val select2 = data[j]
            for (k in j + 1..<caseSize) {
                val select3 = data[k]

                for (l in 0..<4) {
                    if (select1[l] != select2[l]) {
                        count++;
                    }
                    if (select1[l] != select3[l]) {
                        count++;
                    }
                    if (select2[l] != select3[l]) {
                        count++;
                    }
                }
                minValue = min(minValue, count)
                count = 0
            }
        }
    }
}