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

문제 요약

• 알고리즘 분류: 브루트포스, 비둘기 집 원리
• 난이도: Silver1
• 문제내용:
  • mbti N개에서 세 사람의 심리적인 거리를 구한다.
  • 심리적거리는 각 두 사람 차이의 개수이고 A, B, C의 각 각 거리를 합한것이다.
  • 가장 가까운  심리적 거리를 구하여
• 사이트 주소: https://www.acmicpc.net/problem/20529

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

문제풀이

 이번 문제는 브루트포스와 비둘기 집원리 문제이다. 비둘기 집 원리 개념은 아래 글로 확인해보면된다.

https://namu.wiki/w/%EB%B9%84%EB%91%98%EA%B8%B0%20%EC%A7%91%EC%9D%98%20%EC%9B%90%EB%A6%AC

비둘기 집의 원리

 비둘기 집 원리 간단하게 설명하면 최소한 몇 명일때 3 사람 중 다 같은 mbti가 나올 것인다. 여기 왜 비둘기 집 원리가 들어가는 이유는 모두다 탐색 하면 O(N^3)이상 시간이 나오는 점에서 시간 초과가 나올 가능성이 크다. 그래서 시간 초과 문제를 해결 하기 위해서 비둘기 집의 원리로 풀어야 한다.  3 사람이  다 같은 mbti이면 심리적 거리는 0이고 문제에서 나올 수 있는 최소 값이다. 그러면 그 최소 몇명이면 바로 0으로 출력하면되고 모든 경우의 수를 구할 필요가 없기 때문이다. 그러면 최소 몇명인게 문제인데 최소 33명일때 같은 mbti 3명이 나온다.  그래서 33명 이상이면 0으로 바로 출력 하면된다.

이제 나머지는 세사람 뽑는것과 심리적 거리 구현만 하면된다.

 

N개 에서 세 사람 뽑기

Python

result = 12 # 심리적 거리 최대 값

for i in range(N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            result = min(distance([mbtis[i], mbtis[j], mbtis[k]]), result)

Java

int result = 12; // 심리적 거리 최대 거리
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, 
                    distance(new String[]{mbtis[i], mbtis[j], mbtis[k]}));
        }
    }
}

심리적 거리 계산

Python

def distance(mbti):
    dist = 0
    for i in range(4):
        dist += mbti[0][i] != mbti[1][i]
        dist += mbti[0][i] != mbti[2][i]
        dist += mbti[1][i] != mbti[2][i]

    return dist

Java

public static int distance(String[] mbti) {
    int dist = 0;
    for(int i = 0; i < 4; i++) {
        dist += mbti[0].charAt(i) != mbti[1].charAt(i)? 1:0;
        dist += mbti[0].charAt(i) != mbti[2].charAt(i)? 1:0;
        dist += mbti[1].charAt(i) != mbti[2].charAt(i)? 1:0;
    }

    return dist;
}

 

비둘기 집 원리, 심리적 거리 계산, 3명 뽑는것 3가지만 고려해서 구현 하면 쉽게 문제 풀수가 있다.

Code

Python

# 심리적 거리
def distance(mbti):
    dist = 0
    for i in range(4):
        dist += mbti[0][i] != mbti[1][i]
        dist += mbti[0][i] != mbti[2][i]
        dist += mbti[1][i] != mbti[2][i]

    return dist



for _ in range(int(input())):
    N = int(input())
    mbtis = input().split()

    if N > 32:
        print(0)
    else:
        result = 12 # 심리적 거리 최대 값

        for i in range(N):
            for j in range(i + 1, N):
                for k in range(j + 1, N):
                    result = min(distance([mbtis[i], mbtis[j], mbtis[k]]), result)

        print(result)

Java

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N;
		String[] mbtis;
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			N = Integer.parseInt(br.readLine());
			mbtis = new String[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				mbtis[i] = st.nextToken();
			}
			if(N > 32) {
				System.out.println(0);
			}else {
				int result = 12; // 심리적 거리 최대 거리
				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, 
									distance(new String[]{mbtis[i], mbtis[j], mbtis[k]}));
						}
					}
				}
				System.out.println(result);
			}
			
		}
		
	}
	
	/*
	 * 심리적 거리
	 */
	public static int distance(String[] mbti) {
		int dist = 0;
		for(int i = 0; i < 4; i++) {
			dist += mbti[0].charAt(i) != mbti[1].charAt(i)? 1:0;
			dist += mbti[0].charAt(i) != mbti[2].charAt(i)? 1:0;
			dist += mbti[1].charAt(i) != mbti[2].charAt(i)? 1:0;
		}
		
		return dist;
	} 

}