[백준] 20529번 가장 가까운 세 사람의 심리적 거리(비둘기집 원리_JAVA)

완전탐색으로 풀었을 때

시간초과가 발생해서

고민하다가 검색해서 풀게 된 문제

 

완전탐색은 맞지만,

가지치기를 생각해야 한다!

 

---

문제

 

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

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

 

 

---

설계

 

알고리즘 설계 [접근방법] : 비둘기집 원리

비둘기집 원리는 이 문제로 처음 알게 됐다.

비둘기집 원리란 n개의 상자가 존재하고, 비둘기가 n+1마리 존재했을 때, 적어도 한 상자에는 비둘기가 무조건 두 마리 이상 들어가야 한다. 

비둘기가 두 마리 이상 들어있는 상자가 어떤 상자인지는 알 수 없지만, 두마리 이상 들어있다는 것만은 안다.

예시로 13명이 있을 때, 생일이 같은 달인 사람은 최소 2명 이상 존재한다.

 

이 문제에서도, 사람이 3명에서 10만명까지 입력받을 수 있다.

그런데 mbti 종료는 16개이므로, 사람이 17명이면 같은 mbti가 무조건 2명 이상이 나온다.

그리고 33명 이상이면 같은 mbti가 무조건 3명이상 나온다.

그러므로 사람의 수가 33명 이상으로 입력받으면 계산할 필요없이 0을 출력하면 된다.

 

그 이하는 완전탐색으로 풀 수 있다.

 

풀이 과정

1.

테스트케이스의 수 test를 입력받는다.

 

2.

1개의 테스트케이스마다 사람의 수인 n을 입력받는다.

그 후 n명 만큼 mbti를 입력받고, 배열 mbti에 저장한다.

만약 n이 33 이상이면 0을 출력하고 다음으로 넘어간다.

 

3.

n이 33이 아니라면, 3중 반복문으로 3명의 mbti의 차이가 얼만큼인지 메서드 distance로 확인 한다.

메서드 distance에서든 3개의 문자열을 문자 배열로 바꾼 후,  mbti의 알파벳을 하나 하나 비교하고 다른 개수를 센다.

 

4.

최소값을 구하기 위해 min과 비교한 후, 3중 반복문이 종료되었을 때 min을 출력한다.

 

 

---

코드

 

import java.util.*;


public class Test_20529_가장가까운세사람의심리적거리 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//비둘기 원리
		//n이 33이상이면 같은 mbti가 3명이 생긴다. > 계산 불필요
		//그 전까지 완전탐색
		
		int test = sc.nextInt();
		for(int t=0; t<test; t++) {
			
			int n = sc.nextInt();

			int min = Integer.MAX_VALUE;
			
			String[] mbti = new String[n];
			for(int i=0; i<n; i++) {
				mbti[i] = sc.next();
			}
			
			if(33<=n) {
				System.out.println("0");
				continue;
			}
			
			for(int i=0; i<mbti.length; i++) {
				for(int j=i+1; j<mbti.length; j++) {
					for(int k=j+1; k<mbti.length; k++) {
						int count = distance(mbti[i], mbti[j], mbti[k]);
						min = Math.min(min, count);
					}
				}
			}
			
			//출력
			System.out.println(min);
			
		}
	}
	
	
	//세사람 거리 계산하기
	public static int distance(String str1, String str2, String str3) {
		
		char[] charArr1 = str1.toCharArray();
		char[] charArr2 = str2.toCharArray();
		char[] charArr3 = str3.toCharArray();
		
		int count = 0;
		for(int i=0; i<charArr1.length; i++) {
			if(charArr1[i]!=charArr2[i]) count++;
			if(charArr1[i]!=charArr3[i]) count++;
			if(charArr2[i]!=charArr3[i]) count++;
		}
		
		return count;
	}
}

 

 

(❁´◡`❁)

끝!