2 분 소요

[Silver I] 가장 가까운 세 사람의 심리적 거리 - 20529

문제 링크

성능 요약

메모리: 38536 KB, 시간: 424 ms

분류

브루트포스 알고리즘, 비둘기집 원리

제출 일자

2024년 4월 13일 22:22:56

문제 설명

여러분은 요즘 유행하는 심리검사인 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는 총 24=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 성격 유형을 나타내는 문자열들이 사이에 공백을 두고 주어진다.

출력

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

풀이

먼저 처음에 접근했다가 실패한 풀이방법이다. 

 import sys
 input = sys.stdin.readline

 T = int(input())

 for i in range(T):
     person = int(input())
     MBTI = list(input().rstrip().split())

     start_index = 0
     sum_ = []
     count = 0

     while start_index <= person-1:
         for compare in range(start_index+1, person):
             for c in range(4):
                 if MBTI[start_index][c] != MBTI[compare][c]:
                     count += 1
             sum_.append(count)
             count = 0
         start_index += 1
    
    # 작성하다가 막힌 코드
     if len(sum_) <= 3 or not sum(sum_):
         print(sum_)
     else:

첫번째와 두번째 테스트 케이스는 성공했지만 세번째는 실패했다. 사람이 3명 이하이거나 모두 같은 MBTI인 경우에는 심리적 거리가 쉽게 구해진다. 하지만 사람이 3명이상인 경우, 그 중에서 심리적 거리가 가장 가까운 3명을 구해야 하기 때문에 최소값을 추출하는 알고리즘이 도무지 생각나지 않았다.

일단 그전에 count리스트에는 거리값만 저장된 리스트이기 때문에 어느 조합이 어떤 거리값을 가지는지 구분할 수 없었다. 그리고 3가지를 비교해야 하는데 2개씩만 비교를 3가지를 추려내기엔 어려움이 컸다. 결국 다른 분들의 풀이를 참고하여 풀어보았다.

전체 코드

import sys
input = sys.stdin.readline

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

T = int(input())

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

    if N > 32:
        print(0)
    else:
        min_distance = 12
        for i in range(N):
            for j in range(i+1, N):
                for k in range(j+1, N):
                    min_distance = min(distance([MBTI[i], MBTI[j], MBTI[k]]), min_distance)
        print(min_distance)

댓글남기기

참고