[백준] 가장 가까운 세 사람의 심리적 거리 : 20529 : Java - 완전 탐색(S1)

1. 문제

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

 

 

• 세 명의 심리적 거리를 구하고 가장 최솟값을 찾는다.
• 세명의 심리직 거리 = (A와 B의 심리적 거리) + (B와 C의 심리적 거리) + (C와 A의 심리적 거리)
• MBTI는 겹칠 수도 있으며, 같은 MBTI간의 심리적 거리는 0이다.

 

---

 

2. 풀이 생각

문제는 가장 최소가 될 수 있는 세명을 어떻게 찾느냐이냐. 세명을 찾기 위해 완전 탐색을 하게 되면 십만X십만X십만으로 10의 15승이 되고, 시간초과가 난다. 그러므로 완전 탐색은 방법이 아니다. 방법은 mbti의 종류가 16개인 것을 이용하는 것이다.

 

사람의 수가 아무리 많아도 MBTI는 16종류이다. 게다가 심리적 거리는 오로지 MBTI로만 결정된다. 그러므로 각 MBTI마다 몇 명의 사람이 나오는지 카운트하고 세 사람을 뽑기 위해 MBTI 종류별로 사람을 뽑는 과정을 반복하여 완전탐색을 진행한다.그 중에서 세 사람의 심리적 거리를 구한 후 최솟값을 갱신하며, 최솟값을 알아낸다. 16종류 이므로 3중 루프를 돌아도 16x16x16으로 4096번의 계산이면 한 테스트 케이스의 답을 구할 수 있다.

 

하지만 이 때, MBTI별로 사람의 수를 잘 세어서 중복이 가능한지 잘 확인해야한다. 만약 ISTJ를 가진 사람이 단 한 명뿐일 때 첫 번째 친구로 ISTJ를 뽑아놓고 두 번째, 세 번째 친구로 다시 ISTJ를 뽑지 않아야한다.

 

또한 사람의 수 `N`이 33명 이상인 경우 무조건 같은 MBTI를 가진 사람이 3명이 존재한다. 왜냐하면 16종류이기 때문에, 17명일 때는 무조건 같은 MBTI를 가진 사람이 2명 존재하고, 33명일 때는 3명이 무조건 존재한다. 그러므로 이때는 바로 0를 출력하여 탐색시간을 줄일 수도 있다.

 

 

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 =1; t<=T; t++){
            HashMap<String, Integer> mbtiContainer = new HashMap<>();

            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 무조건적으로 3명의 MBTI가 겹칠 때
            if(N >32){
                bw.write(0+"\n");
                continue;
            }

            while(st.hasMoreTokens()){
                String mbti = st.nextToken();
                int count = mbtiContainer.getOrDefault(mbti, 0) +1;
                mbtiContainer.put(mbti, count);
            }

            String[] existMbtis = mbtiContainer.keySet().toArray(new String[0]);
            int result = Integer.MAX_VALUE;
            for(int i=0; i<existMbtis.length; i++){
                // 첫번쨰 친구와 두 번쨰 친구
                for(int j=0; j< existMbtis.length; j++){
                    // 중복인데 해당 mbti가 1명뿐이면 패스
                    if(i==j && mbtiContainer.get(existMbtis[i]) == 1)
                        continue;
                    // 친구 1과 친구 2의 관계
                    int s1ToS2 = getMindDistance(existMbtis[i], existMbtis[j]);

                    for(int k=0; k<existMbtis.length; k++){
                        // 해당 MBTI를 가진 사람이 1명 이하이면 중복은 불가하므로 패스
                        if(i==k && mbtiContainer.get(existMbtis[i]) <= 1)
                            continue;
                        if(j==k && mbtiContainer.get(existMbtis[j]) <= 1)
                            continue;
                        // 친구 1과 친구 2,친구 3까지 같을 때 해당 mbti를 가진 사람이 3명 미만이면 패스
                        if(i==j && j==k && mbtiContainer.get(existMbtis[i]) <=2)
                            continue;

                        int s2ToS3 = getMindDistance(existMbtis[j], existMbtis[k]);
                        int s1ToS3 = getMindDistance(existMbtis[i], existMbtis[k]);
                        result = Math.min(result, s1ToS3 + s2ToS3 + s1ToS2);
                    }
                }
            }
            bw.write(result+"\n");
        }
        bw.flush();

        bw.close();
        br.close();
    }

    public static int getMindDistance(String s1, String s2){
        // 글자가 다르면 count 증가
        int count = 0;
        for(int i =0; i<4; i++){
            if((s1.charAt(i) != s2.charAt(i)))
                count++;
        }
        return count;
    }
}