[백준 20529] 가장 가까운 세 사람의 심리적 거리 (Silver 1)

문제

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

접근

• 완전 탐색을 할 경우 O(N^3)의 시간 복잡도로 인해 TLE가 나온다. 이 문제는 비둘기 집 원리를 이용해 시간 복잡도를 줄일 수 있다.
• 모든 MBTI마다 쌍으로 묶여있다고 가정해보자. 이 때 n의 개수는 32개이다.
• n이 33 이상일 경우 심리적 거리가 반드시 0인 경우가 존재한다.
  ex) n이 33일 때, 쌍으로 묶여있는 MBTI (32개)와 ENFJ가 주어졌다고 가정해보자. 뭔 짓을 해도 가장 가까운 심리적 거리가 0이 나오는데, (ISTP, ISTP, ENFJ) 경우가 가장 작은 심리적 거리가 된다.

Code

import sys

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    mbti = sys.stdin.readline()
    if n > 32:
        print(0)
    else:
        mbti = mbti.split()
        answer = sys.maxsize
        for i in range(len(mbti)):
            for j in range(len(mbti)):
                for k in range(len(mbti)):
                    if i == j or j == k or k ==i:
                        continue
                    cnt = 0
                    for x in range(4):
                        if mbti[i][x] != mbti[j][x]:
                            cnt += 1
                        if mbti[j][x] != mbti[k][x]:
                            cnt += 1
                        if mbti[i][x] != mbti[k][x]:
                            cnt += 1
                    answer = min(answer, cnt)
        print(answer)