[백준 20529] 가장 가까운 세 사람의 심리적 거리 (JAVA)

백준 20529번 문제 - 가장 가까운 세 사람의 심리적 거리

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

---

문제 분석 

 

• MBTI 성격 유형을 이용하면 두 사람 사이의 심리적인 거리를 정의할 수 있다.
• 이는 두 사람의 MBTI 유형에서 서로 다른 분류에 속하는 척도의 수로 정의된다.
  • ex) ISTJ인 사람과 ISFJ인 사람 사이의 거리는 1
  • ex) INTP인 사람과 ENTJ인 사람 사이의 거리는 2
• 세 사람 A,B, C가 있을 때 이들의 심리적인 거리 = (A, B 심리적 거리) +  (A, C 심리적 거리) +  (B, C 심리적 거리)
• N명의 학생들의 MBTI 유형이 주어질 때, 가장 가까운 세 학생 사이의 심리적인 거리를 출력해라

 

• 추가적 제한

 

---

해결 포인트

 

• 완전 탐색
• 시간 초과 주의
  • 가장 작은 값으로 0이 나오면 종료시켜 시간 단축
  • N이 33 이상일 경우 가장 작은 값은 무조건 0으로 확인 안하여 시간 단축
    - WHY? mbti 개수는 16개이므로 17(16+1)개면 2명은 반드시 겹치고, 33(16+16+1)개면 3명은 반드시 겹치기 때문에

---

코드

 

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            ArrayList<char []> mbti = new ArrayList<>();

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                mbti.add(st.nextToken().toCharArray());
            }

            int min = 100001;

            if(N >= 33)
                min = 0;

            for (int i = 0; i < N-2; i++) {
                if(min == 0) break;
                for (int j = i+1; j < N-1; j++) {
                    for (int l = j+1; l < N; l++) {
                        int sum = 0;

                        char [] mbti1 = mbti.get(i);
                        char [] mbti2 = mbti.get(j);
                        char [] mbti3 = mbti.get(l);
                        for (int k = 0; k < 4; k++) {
                            if(mbti1[k] != mbti2[k])
                                sum++;
                            if(mbti1[k] != mbti3[k])
                                sum++;
                            if(mbti2[k] != mbti3[k])
                                sum++;
                        }
                        min = Math.min(min, sum);
                    }
                }
            }

            bw.write(min + "\n");
        }

        bw.flush();
        bw.close();
    }
}