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

난이도 / 문제 링크

Silver 1

 

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

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

 

 

 

---

 

 

 

풀이

비둘기집 원리?? 라고 하는데 처음들어본다

https://ko.wikipedia.org/wiki/%EB%B9%84%EB%91%98%EA%B8%B0%EC%A7%91_%EC%9B%90%EB%A6%AC

비둘기집 원리 - 위키백과, 우리 모두의 백과사전

 

모르는 상태에서 단순 든 생각을 정리해보았다.

1. 완전 탐색을 통해 모든 경우의 수에서 최소값을 구하며, 시간 단축을 위해 과정에서 0이 나왔을 경우 break

 

2. 테스트 케이스는 50이하, 사람 수는 100,000명 이하인데 100,000명이라고 가정했을 때, 3명씩 나눠서 반복하고 나눈 사람들을 또 charAt와 같은 String 메서드를 통해 체크해주어야 하기 때문에 시간 + 메모리 둘다 초과할 거라고 생각했다. 방법을 찾아야 했는데, 2번 예제에서 힌트를 얻었다.

 

반드시 0이 나오는 경우가 언제일까를 고민했고, 사람 수가 33명 이상일 때 라는 결론을 내릴 수 있었다.

MBTI는 16종류기 때문에, 17명이상일 때 2명이 반드시 겹치고, 33명 이상일 때 3명이 반드시 겹치는 경우가 발생할 수 밖에 없다.

 

1,2번을 종합하여 Brute Force를 구현하면서도 시간이나 메모리를 덜 사용할 수 있게 코드를 작성했다.

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

public class BaekJoon20529 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine(), " ");

            if(N > 32) {
                System.out.println(0);
                continue;
            }

            String[] MBTI = new String[N];

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

            int min = Integer.MAX_VALUE;

            for(int j = 0; j < N; j++) {
                for(int k = j+1; k < N; k++) {
                    for(int l = k+1; l < N; l++) {
                        int cnt = 0;
                        for(int m = 0; m < 4; m++) {
                            cnt += MBTI[j].charAt(m) != MBTI[k].charAt(m) ? 1 : 0;
                            cnt += MBTI[j].charAt(m) != MBTI[l].charAt(m) ? 1 : 0;
                            cnt += MBTI[k].charAt(m) != MBTI[l].charAt(m) ? 1 : 0;
                        }
                        min = Math.min(cnt, min);
                        if(min == 0) break;
                    }
                }
            }
            System.out.println(min);
        }
    }
}