20529번. 가장 가까운 세 사람의 심리적 거리

 

1. 아이디어

1. 브루트포스 방식으로 모든 케이스에 대해서 탐색하되

2. MBTI의 종류가 16가지라 입력값의 갯수가 32개를 초과하면 반드시 동일한 MBTI가 3개 이상 입력값에 존재하므로

3. N > 32 면 0을 N <= 32 면 거리 계산을 직접해준다!!

 

처음에 단순 브루트포스 방식으로 문제를 풀었더니 시간 초과가 나와서 참고 원리 중 '비둘기집 원리'에 대해 알아보고 2, 3번의 방법을 생각해냈다.

 

2. 풀이 코드

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

public class _n20529_ {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            String[] mbtis = br.readLine().split(" ");

            if (N > 32) {
                sb.append("0").append("\n");
                continue;
            }

            int min = 12;

            for (int i = 0; i < N-2; i++) {
                for (int j = i+1; j < N-1; j++) {
                    for (int k = j+1; k < N; k++) {
                        int d = calcDistance(mbtis[i], mbtis[j], mbtis[k]);
                        if (min > d) {
                            min = d;
                        }
                    }
                }
            }
            sb.append(min).append("\n");
        }

        System.out.println(sb);
    }

    public static int calcDistance(String A, String B, String C) {
        int d1 = 0;
        int d2 = 0;
        int d3 = 0;

        for (int i = 0; i < 4; i++) {
            if (A.charAt(i) != B.charAt(i)) {
                d1++;
            }

            if (B.charAt(i) != C.charAt(i)) {
                d2++;
            }

            if (C.charAt(i) != A.charAt(i)) {
                d3++;
            }
        }

        return d1 + d2 + d3;
    }
}