문제 설명

mbti가 최대 10만명에 대해 주어진다. mbti의 종류는 16개다.
ISTJ와 ISFJ 사이의 심리적 거리는 T와 F가 다르므로 1이다.
이때, 이 10만명 중 세 사람의 거리가 가장 작은 값을 구하라.

접근

시간 제한이 2초에 10만명 밖에 안돼서 브루트 포스로 먼저 생각해봤는데 일단 뭐 어떻게 풀어도 시간초과는 나지 않는다는 것을 확신했다. 하지만, 아무래도 두 문자열의 동일위치에 존재하는 문자를 비교해야하기 때문에 최대한 집합 개념을 써서 불필요한 중복 연산을 줄이려고 노력했다.
삼중 for문을 써서 문제를 풀었고 400ms대가 나왔다. 그런데, 다른 사람들의 풀이 시간을 찾아보니 자바로 196ms까지 나오길래 들여다 보았다.
입력으로 들어온 사람의 수가 48명 이상이면 0을 반환하고 있었다.
생각해보니 사람의 수가 48명을 넘는다면, 16종류의 mbti 중 최소한 하나 이상은 그 mbti가 3명이상인 것이다.
동일 mbti 세명이면 심리적 거리의 합은 0이므로 시간을 획기적으로 줄일 수 있었다.

최종 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static HashMap<String, HashMap<String, Integer>> doubleMap = new HashMap<>();
    static String[] mbtis = {
            "ISTJ", "ISFJ", "INFJ", "INTJ",
            "ISTP", "ISFP", "INFP", "INTP",
            "ESTP", "ESFP", "ENFP", "ENTP",
            "ESTJ", "ESFJ", "ENFJ", "ENTJ"
    };

    static int mbtiDistance(String a, String b) {
        int result = 0;
        for (int i = 0; i < 4; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                result++;
            }
        }
        return result;
    }

    static int mbtiTripleDistance(String a, String b, String c) {
        return doubleMap.get(a).get(b) + doubleMap.get(a).get(c) + doubleMap.get(b).get(c);
    }

    public static void main(String[] args) throws IOException {
        // 두 사람의 관계를 먼저 초기화
        for (String a : mbtis) {
            doubleMap.put(a, new HashMap<>());
            HashMap<String, Integer> map = doubleMap.get(a);
            for (String b : mbtis) {
                map.put(b, mbtiDistance(a, b));
            }
        }

        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int arrSize = Integer.parseInt(br.readLine());
            if (arrSize >= 48) {
                sb.append(0).append("\n");
                br.readLine();
                continue;
            }
            String[] inputMbtis = br.readLine().split(" ");

            int result = Integer.MAX_VALUE;
            for (int i = 0; i < inputMbtis.length; i++) {
                for (int j = i + 1; j < inputMbtis.length; j++) {
                    for (int k = j + 1; k < inputMbtis.length; k++) {
                        int sum = mbtiTripleDistance(inputMbtis[i], inputMbtis[j], inputMbtis[k]);
                        result = Math.min(sum, result);
                    }
                }
            }
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

느낀점

일단 자바로 풀려니까 아직까지는 과도기인지 좀 불편하고 문법을 한 번 더 생각하느냐고 뇌정지가 오고 있다. 코틀린이였으면 Pair를 썼을텐데 그게 없어서 이중 HashMap을 쓰는 것도 배웠고, 종류의 갯수가 제한적이고 그 종류 중 하나라도 일정수를 넘으면 답이 영향을 받는 경우에는 비둘기집을 사용할 수 있다는 것을 배웠다.