[BaekJoon] 20529번 가장 가까운 세 사람의 심리적 거리 (Java) 문제 풀이 [Silver 1]

문제

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

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

 

어떻게 풀 것인가?

모든 경우를 찾는 브루트포스 문제였다. 다만 조건을 걸지 않으면 O(N^3)이 발생해서, 시간초과가 발생한다.

 

그렇다면 어떠한 조건으로 거를 수 있을까?

 

첫번째, 심리적 거리가 최악인 경우는 0이다. 즉, 0이 발생하면 반복문을 중단하면된다.

 

두번째, 서로 다른 MBTI는 16명이다. 2명씩 총 32명 있을 경우 심리적 거리는 0이 될 수 있다.

 

33명부터 동일한 MBTI를 가진 인원이 3명이 되기 때문에 비로소 심리적 거리가 0임을 보장할 수 있다.

 

풀면서 놓쳤던점

조건이 까다로워서 시간초과가 많이 발생했다.

 

이 문제를 통해 얻어갈 것

브루트포스를 활용한 비둘기집 알고리즘 원리를 배울 수 있었다.

 

내 코드 

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

// 백준알고리즘 20529번 가장 가까운 세 사람의 심리적 거리

public class Main {
    static int T;

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

        for (int test_case = 0; test_case < T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            String[] arr = new String[N];
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int i = 0; i < N; i++) {
                arr[i] = st.nextToken();
            }

            if (N >= 33) {
                sb.append(0).append("\n");
            } else {
                int min = Integer.MAX_VALUE;
                for (int i = 0; i < N; i++) {
                    for (int j = i + 1; j < N; j++) {
                        for (int z = j + 1; z < N; z++) {
                            min = Math.min(min, calDistance(arr[i], arr[j], arr[z]));
                            if (min == 0) break;
                        }
                    }
                }
                sb.append(min).append("\n");
            }
        }

        System.out.print(sb);
    }

    public static int calDistance(String person1, String person2, String person3) {
        int sum = 0;
        for (int i = 0; i < 4; i++) {
            sum += (person1.charAt(i) != person2.charAt(i) ? 1 : 0);
            sum += (person2.charAt(i) != person3.charAt(i) ? 1 : 0);
            sum += (person1.charAt(i) != person3.charAt(i) ? 1 : 0);
        }
        return sum;
    }
}

 

참고

X