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

문제 풀이

---

이번 문제는 문제의 제약사항을 잘 파악한 뒤, 완전탐색을 이용해 쉽게 풀 수 있다.

아이디어 도출

처음에 단순히 완전탐색을 통해 모든 경우를 탐색하려 했으나 N의 범위가 최대 100,000이기에 시간초과를 어느정도 고려해야 했다.

시간 초과를 어떻게 줄일 수 있을까?

우리는 가까운 3 사람의 MBTI를 통해 최소가 되는 심리거리를 구해야 한다. 문제에서 주어지는 MBTI는 총 16가지이며 이것이 큰 힌트가 된다.

세 사람의 MBTI가 같다면, 서로간의 심리거리는 0으로 가장 최소가 될테니 이후로는 더이상 탐색할 필요가 없다.

그런데 MBTI는 한 사람당 16가지 중 1가지가 나오며 두 사람일 경우는 32가지가 된다. 33가지가 넘어가는 순간 세 사람이 같은 MBTI가 될 수 있기 때문에 33명의 학생(N)을 입력받을 경우 묻지도 않고 따지지도 않고 0을 출력하면 나머지 탐색을 줄일 수 있어 시간복잡도 측면에서 이득이 된다.

그렇다면 이제 아이디어를 정리해보자.

1. N(학생)이 33 이상이 주어질 경우 0을 출력하고 다음 순회로 넘어간다.
2. N이 32 이하일 경우 3중 for문(세 사람)으로 완전 탐색을 하며 서로 간의 심리거리를 구하고 이 심리거리들 중 최솟값으로 갱신한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    public static void main(String[] args) throws IOException {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {

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

                while(T --> 0) {

                    int N = Integer.parseInt(br.readLine());
                    StringTokenizer st = new StringTokenizer(br.readLine());

                    /**
                     * 세 사람의 심리적 거리가 0이 될 경우 최소이기에 더 탐색을 진행할 필요가 없다.
                     * MBIT의 종류는 총 16가지이기에 N이 33 이상이라면 중복되는 3개의 MBTI가 주어질 수 있기에 불필요한 탐색을 하게 된다.
                     * N이 33 이상이라면 바로 0을 반환할 수 있도록 한다.
                     */
                    if(N > 32) {
                        bw.write("0" + "\n");
                        continue;
                    }

                    // * N이 32 이하일 경우 아래 로직을 수행한다.

                    // N개의 MBTI 문자열을 입력받는다.
                    String[] mbtis = new String[N];
                    for(int i=0; i<N; i++) {
                        mbtis[i] = st.nextToken();
                    }

                    // 세 사람의 심리거리의 최소값을 구하기 위한 변수 초기화한다.
                    int result = Integer.MAX_VALUE;

                    // N개 중 3 사람의 조합을 이용해 최소가 되는 심리거리를 구한다.
                    for(int i=0; i<N; i++) {
                        for(int j=i+1; j<N; j++) {
                            for(int k=j+1; k<N; k++) {
                                result = Math.min(result, getDistance(mbtis[i], mbtis[j], mbtis[k]));
                            }
                        }
                    }

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

        }

    }

    // 3개의 MBTI를 통해 심리거리를 구하는 함수
    public static int getDistance(String a, String b, String c) {
        int result = 0;
        for(int i=0; i<4; i++) {
            if(a.charAt(i) != b.charAt(i) ) {
                result++;
            }
            if(b.charAt(i) != c.charAt(i)) {
                result++;
            }
            if(a.charAt(i) != c.charAt(i)) {
                result++;
            }
        }
        return result;
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.