[BOJ 20529] 가장 가까운 세 사람의 심리적 거리(비둘기집 어렵지 않아요!!!!!! 초간단)

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

// 가장 가까운 세 사람의 심리적 거리
public class Main {
    // 테스트 케이스 T
    // 학생 후 N,
    // 엠비티아이 각각의 수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // T
        int[] arr = new int[T];

        for (int i = 0; i < T; i++) {
            Integer N = Integer.parseInt(br.readLine()); // N
            String MBTIs = br.readLine();
            String[] mbti = MBTIs.split(" ");

            int result = checkThreeNum(mbti);
            arr[i] = result;
        }

        // 출력
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    private static int checkThreeNum(String[] mbti) {
        if (mbti.length > 33) return 0;
        int min = 8; // 최대값이 8

        for (int j = 0; j < mbti.length; j++) {
            for (int k = j + 1; k < mbti.length; k++) {
                for (int l = k + 1; l < mbti.length; l++) {
                    int sum = 0;

                    for (int i = 0; i < 4; i++) {
                        if (mbti[j].charAt(i) != mbti[k].charAt(i) || mbti[k].charAt(i) != mbti[l].charAt(i)) sum += 2;
                    }

                    if (min > sum) min = sum;
                }
            }
        }
        return min;
    }
}

떠올린 접근 방식, 과정

1. 입력받은 엠비티아이 중 3가지를 선택한다.
2. 선택한 3가지의 각 자리수를 비교한다.
   1. 이때 모든 글자가 다 같다면 거리는 0이 되고 그렇지 않다면 2가 된다.
3. 모든 엠비티아이에 대해 이 과정을 반복한다.
4. 최소값을 반환한다.

해당 접근 방식에 쓰이는 알고리즘과 판단 사유

bruteforce 사용

생각나는 게 없었다… 시간 초과가 걸릴 것 같았지만 냅다 했다.

접근법의 총 시간복잡도

O(N^5)

(에러 오류가 발생했다면) 해결 과정

역시나 시간초과가 발생했다. 처음 생각한 원인은

• 동일한 엠비티아이가 2개 있을 때
  • 모든 엠비티아이에 대해 비교를 하기 때문에 동일한 엠비티아이가 2개라면 같은 비교를 2번하게 된다. (동일한 게 3개라면 당연히 거리가 0이고 정답)

ex. INFP INFP ESTP ESTJ ISTJ 라면 INFP ESTP ESTJ 와 같은 INFP의 비교가 2번 실행되는 것!

 

mbti가 다 같은 경우, 2개만 같은 경우, 다 다른 경우 나누어 재구현했지만 삽질이고 크게 개선되지 않는 것 같아 구글링을 하였다…

개선 방법

비둘기집 원리를 이용하면 아주 간단하게 시간초과에서 벗어날 수 있었다.

비둘기집 원리란?

• 과일의 종류가 3개 있고 과일의 개수가 총 4개라면 한 과일은 적어도 2개 이상 존재한다.
• 즉 우리 예제에 비추어보면 mbti는 16종류이기 때문에 사람이 17명이라면 적어도 한 mbti는 2명 이상 존재

→ 그렇다면 사람이 33명이라면 적어도 한 mtbi를 가지는 사람이 3명이상이 되고 거리는 무조건 0이 되는 것!!

이 원리를 이용하여 N이 33이거나 클 경우 무조건 0을 반환하도록 코드를 변경하였다!