[백준] 20539번 가장 가까운 세 사람의 심리적 거리 [Python] - 비둘기집 원리

 

 

두 사람의 서로 다른 유형의 개수를 두 사람의 거리라고 했을 때,

세 사람의 거리를 a와 b의 거리 + b와 c의 거리 + c와 a의 거리의 합라고 하자

N명의 사람들 중에서 세 사람의 거리 중 최소를 출력하는 문제

 

문제

여러분은 요즘 유행하는 심리검사인 MBTI에 대해 들어보았는가?

MBTI$($Myers-Briggs Type Indicator$)$는 C.G.Jung의 심리유형론을 근거로 하여 Katharine Cook Briggs와 Isabel Briggs Myers가 보다 쉽고 일상생활에 유용하게 활용할 수 있도록 고안한 자기보고식 성격유형지표이다. $($출처: 위키백과$)$

MBTI는 아래와 같이 네 가지 척도로 사람들의 성격을 구분한다.

• 외향$($E$)$ / 내향$($I$)$
• 감각$($S$)$ / 직관$($N$)$
• 사고$($T$)$ / 감정$($F$)$
• 판단$($J$)$ / 인식$($P$)$

각 척도마다 두 가지 분류가 존재하므로, MBTI는 총 $2^4 = 16$가지 유형이 있음을 알 수 있다. 일반적으로 MBTI의 유형들은 각 분류를 나타내는 알파벳 한 글자씩을 따 네 글자로 표시하게 된다. 모든 유형의 목록은 다음과 같다.

• ISTJ, ISFJ, INFJ, INTJ, ISTP, ISFP, INFP, INTP, ESTP, ESFP, ENFP, ENTP, ESTJ, ESFJ, ENFJ, ENTJ

MBTI 성격 유형을 이용하면 두 사람 사이의 심리적인 거리를 정의할 수 있다. 이는 두 사람의 MBTI 유형에서 서로 다른 분류에 속하는 척도의 수로 정의된다. 예를 들어, MBTI 유형이 ISTJ인 사람과 ISFJ인 사람 사이의 거리는 1이며, INTP인 사람과 ENTJ인 사람 사이의 거리는 2이다.

이 정의를 확장해서 세 사람 사이의 심리적인 거리도 정의할 수 있다. 세 사람 A, B, C가 있을 때 이들의 심리적인 거리는

$($A와 B 사이의 심리적인 거리$) + ($B와 C 사이의 심리적인 거리$) + ($A와 C 사이의 심리적인 거리$)$

로 정의한다.

대학교에서 심리학 교수로 일하는 종서는 자신이 가르치는 학생들의 심리적인 특성을 분석하고 싶어한다.

오늘이 생일인 종서를 위해 N명의 학생들의 MBTI 유형이 주어질 때, 가장 가까운 세 학생 사이의 심리적인 거리를 구해보자.

입력

첫 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 학생의 수를 나타내는 하나의 정수 N이 주어지며, 두 번째 줄에는 각 학생의 MBTI 성격 유형을 나타내는 문자열들이 사이에 공백을 두고 주어진다.

출력

각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.

제한

•  $1 \le T \le 50$ 
•  $3 \le N \le 100\,000$ 
• 각 테스트 케이스의 N의 합은 $100\,000$을 넘지 않는다.

 

비둘기 집 원리 >>>

mbti가 같은 사람이 3명이 넘으면 세 사람의 거리가 0인 경우가 생긴다.

mbti의 종류는 16가지로 각 mbti별로 2명씩 있으면 32명이고,

33명이 존재하면 그 중 적어도 하나의 mbti는 해당 인원이 3명이상이 된다. >>> 거리 = 0

 

딕셔너리로 각 mbti를 key로 그 인원수를 value로 저장

value가 3이상이면 거리 = 0 $($총 인원이 32명 이하여도 이 경우가 나타날 수 있음$)$

 

모든 사람 중에서 세 사람씩 뽑아서 서로의 mbti를 비교해서 합산하고 결과 중에서 최솟값만 저장해서 출력한다.

 

다음 두 가지 방식으로 아래 코드를 작성해 봤습니다.

- mbti의 각 척도$($원소$)$별로 비교하는 방식

- 차집합을 개수를 구하는 방식 $($주석으로 달아놓음$)$

import sys
li = []
for _ in range(int(sys.stdin.readline())):
    N = int(sys.stdin.readline())
    if N > 32:
        li.append('0')
        sys.stdin.readline()
        continue
    types = {}
    for mbti in sys.stdin.readline().split():
        types[mbti] = types.get(mbti, 0) + 1
    if max(types.values()) > 2:
        li.append('0')
        continue
    mbtis = []
    for mbti, n in types.items():
        mbtis.extend([mbti]*n)
    M = len(mbtis)
    s = 12
    for i in range(M):
        for j in range(i+1, M):
            for k in range(j+1, M):
            	# mbti의 각 척도를 각각 비교해서 합산하고 최솟값으로 업데이트
            	s = min(s, sum((a!=b)+(b!=c)+(c!=a) for a, b, c in zip(mbtis[i], mbtis[j], mbtis[k])))
                
                # 차집합의 개수를 구해 합산하고 최솟값으로 업데이트
                # s = min(s, len(set(mbtis[i]) - set(mbtis[j]))+len(set(mbtis[j]) - set(mbtis[k]))+len(set(mbtis[k]) - set(mbtis[i])))
    li.append(str(s))
print("\n".join(li))

 

 

 

collections.Counter를 사용해서 mbti별 개수를 저장한 dict 생성

Counter의 most_common 함수를 사용해서 mbti별 최대 인원이 3명 이상인지 확인

itertools.combinations를 사용해 3명의 조합을 생성해서 비교

import sys
from collections import Counter
from itertools import combinations
li = []
for _ in range(int(sys.stdin.readline())):
    N = int(sys.stdin.readline())
    if N > 32:	# 비둘기집 원리 
        li.append('0')
        sys.stdin.readline()
        continue
        
    types = Counter(sys.stdin.readline().split())
    if types.most_common(1)[0][1] > 2:
        li.append('0')
        continue
        
    mbtis = types.elements()
    cbs = combinations(mbtis, 3)
    s = 12
    for cb in cbs:
        s = min(s, sum(((a!=b)+(b!=c)+(c!=a)) for a, b, c in zip(*cb)))
        if s == 2: break
    li.append(str(s))
    
print("\n".join(li))

 

 

 

예제 입력 1 

3
3
ENTJ INTP ESFJ
4
ESFP ESFP ESFP ESFP
5
INFP INFP ESTP ESTJ ISTJ

예제 출력 1 

8
0
4

• 첫 번째 테스트 케이스의 경우, ENTJ와 INTP의 심리적인 거리는 2, ENTJ와 ESFJ의 심리적인 거리는 2, INTP와 ESFJ의 심리적인 거리는 4이므로 세 사람의 심리적인 거리는 2+2+4=8이다.
• 두 번째 테스트 케이스의 경우, 어떤 사람 둘을 골라도 심리적인 거리가 0이므로 가장 가까운 세 사람의 심리적인 거리는 0이다.
• 세 번째 테스트 케이스의 경우, 심리적인 거리를 최소화하려면 MBTI가 ESTP, ESTJ, ISTJ인 세 사람을 골라야 한다. ESTP와 ESTJ의 심리적인 거리는 1, ESTP와 ISTJ의 심리적인 거리는 2, ESTJ와 ISTJ의 심리적인 거리는 1이므로 세 사람의 심리적인 거리는 1+2+1=4이다.

 

예외 - 현 시점에서는 통과가 되지만 문제가 있는 예제 입력

1
5
INTP INTP ISTP ISTP ISTP

예제 출력

0

답은 0인데, 아래처럼 2를 출력하는 코드도 현재는 정답 처리가 된다.

import sys
from collections import Counter
from itertools import combinations
li = []
for _ in range(int(sys.stdin.readline())):
    N = int(sys.stdin.readline())
    if N > 32:
        li.append('0')
        sys.stdin.readline()
        continue
    cbs = combinations(sys.stdin.readline().split(), 3)
    s = 12
    for cb in cbs:
        s = min(s, sum(((a!=b)+(b!=c)+(c!=a)) for a, b, c in zip(*cb)))
        if s == 2: break
    li.append(str(s))
print("\n".join(li))