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

문제 풀이

백준의 20529번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

가장 먼저 떠오르는 방법은 완전 탐색입니다.

조합을 사용해서 3명씩 뽑은 후 심리적 거리를 계산하는 방법이죠! 그러나.. 거리를 계산하고자 하는 사람의 최대 인원 수는 10만명이기 때문에 시간 초과가 날 것이 분명합니다..!

그런데 잘 생각해보면 세 사람의 심리적 거리 범위의 최소 값은 0이며 3명의 MBTI가 모두 같은 경우입니다. MBTI는 총 16가지의 종류가 있으니 33명 이상 모일 경우에는 반드시 3명 이상이 같은 MBTI를 가지게 됩니다!

이것을 이용해서 33명 이상일 경우에는 무조건 0을 출력하고, 32명 이하일 때만 탐색해서 최소 값을 찾으면 됩니다.

(3) 시간 복잡도 확인

시간 제한은 2초 입니다. 즉, 대략 2억번 연산 안에 문제를 해결해야 합니다.

앞에서 언급했듯이 아무런 조건없이 전부 완전 탐색을 수행하면 시간 초과가 나오기 때문에 32명 이하인 경우에만 조합을 사용하면 됩니다!

(4) 구현

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

public class Main{
    static int n;
    static String[] people;
    static ArrayList<String> list;
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        while(T-->0) {
            result = Integer.MAX_VALUE;
            n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            if(n>=33) {
                bw.append(0 + "\n");
                continue;
            }
            
            people = new String[n];
            list = new ArrayList<>();
            for(int i=0; i<n; i++) {
                people[i] = st.nextToken();
            }
            
            combination(0, 0);
            bw.append(result+"\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }
    
    /***
     * 세 사람의 심리적 거리를 계산하고 최소 값을 갱신하는함수
     */
    static void distance() {
        int sum = 0;
        sum += calculate(list.get(0), list.get(1));
        sum += calculate(list.get(0), list.get(2));
        sum += calculate(list.get(1), list.get(2));
        
        result = Math.min(result, sum);
    }
    
    /***
     * @param a 심리적 거리를 계산하고자 하는 사람 1의 MBTI
     * @param b 심리적 거리를 계산하고자 하는 사람 2의 MBTI
     * @return 계산한 두 사람의 심리적 거리
     */
    static int calculate(String a, String b) {
        int count = 0;
        if(!a.equals(b)) {
            for(int i=0; i<4; i++) {
                if(a.charAt(i) != b.charAt(i)) count++;
            }
        }
        
        return count;
    }
    
    /***
     * @param index 기준 인덱스
     * @param count 뽑은 사람의 수
     */
    static void combination(int index, int count) {
        if(result == 0) return;
        
        if(count==3) {
            distance();
            return;
        }
        
        for(int i=index; i<n; i++) {
            list.add(people[i]);
            combination(i+1, count+1);
            list.remove(list.size()-1);
        }
    }
}