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

문제 링크

https://www.acmicpc.net/problem/20529

풀이

처음에는 조합으로 3개를 선택해서 풀었는데 N이 100,000까지 들어오기 때문에 시간 초과가 난다.

심리적 거리가 0이 될 경우는 모두 같은 mbti인 경우이고, N이 32를 넘는 경우 무조건 심리적 거리가 0이 된다.

왜냐하면 N이 32인 경우 서로 다른 mbti가 입력으로 들어왔을 경우 최소 2개씩 중복되는 mbti가 나온다.

따라서 N이 33이라면 2개로 중복된 mbti가 3개가 되기 때문에 이 때 심리적 거리는 0이 된다.

그래서 입력을 받고 N이 32를 넘는 경우에는 검사를 하지 않고 결과를 0으로 출력한다.

N이 32를 넘지 않는 경우에는 조합으로 3개를 선택해서 심리적 거리를 계산한다.

코드

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

public class Main {
    static int res;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;
        StringBuilder sb = new StringBuilder();

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

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            tokens = new StringTokenizer(br.readLine());

            //32개가 넘으면 무조건 0이 됨. 이미 같은 유형이 2개씩 존재하기 때문
            if (N > 32) {
                sb.append(0).append("\n");
                continue;
            }

            String[] type = new String[N];
            for (int i = 0; i < N; i++) {
                type[i] = tokens.nextToken();
            }

            //조합으로 선택
            res = Integer.MAX_VALUE;
            comb(0, 0, new String[3], type, N);
            sb.append(res).append("\n");

        }
        System.out.print(sb);
    }

    private static void comb(int cnt, int start, String[] s, String[] type, int N) {
        if (cnt == 3) {
            int temp = 0;
            for (int i = 0; i < 4; i++) {
                if (s[0].charAt(i) != s[1].charAt(i)) temp++;
                if (s[0].charAt(i) != s[2].charAt(i)) temp++;
                if (s[1].charAt(i) != s[2].charAt(i)) temp++;
            }
            res = Math.min(res, temp);
            return;
        }

        for (int i = start; i < N; i++) {
            s[cnt] = type[i];
            comb(cnt+1, i+1, s, type, N);
        }
    }
}