시작
처음엔 브루트 포스에 S1짜리 문제길래, 그냥 아래와 같이 냅다 조합을 구해서 다 따져보면 통과가 될 줄 알았다.
from typing import List
from sys import stdin
from math import inf
from itertools import combinations
input = stdin.readline
def get_distance(str1: str, str2: str) -> int:
ret = 0
for i in range(4):
if str1[i] != str2[i]:
ret += 1
return ret
def get_distance_of_3(str1: str, str2: str, str3: str) -> int:
return (
get_distance(str1, str2) + get_distance(str1, str3) + get_distance(str2, str3)
)
def solution(students: List[str]):
ret = inf
for s1, s2, s3 in combinations(students, 3):
ret = min(ret, get_distance_of_3(s1, s2, s3))
return ret
if __name__ == "__main__":
tc = int(input())
for _ in range(tc):
N = int(input())
students = input().split()
print(solution(students))그런데 시간 초과가 나길래 고민 좀 하다가 처음에는 계산했던 거리를 다시 계산하는 문제를 개선하기 위해 딕셔너리를 활용한 일종의 캐시를 적용했었다.
그런데도 시간 초과가 나길래,, 문제를 다시 보니까 태그에 '비둘기집 원리'가 있었다. 해시맵 자료구조의 충돌 가능성과 대처 방법에 대해 공부할 때 '그냥 이렇게도 설명할 수 있구나~~' 하고 넘어갔는데, 알고리즘 문제 해결에도 사용될 수 있다는게 좀 흥미로워서 기록해두려고 한다.
비둘기집 원리 (Pigeonhole principle)
위키 백과에 의하면,,
비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다.
고 한다. 너무 직관적인 명제라서 그냥 그런가보다 하고 넘어갈 수도 있겠지만, 귀류법으로 증명하면 아래와 같다.
n개의 비둘기집과 n+1마리의 비둘기가 있다고 가정한다.
만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 n마리의 비둘기가 존재한다.
그런데 비둘기는 모두 n+1마리이므로, 이것은 모순이다.
따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.
확장
이걸 확장해서 생각해보면, 각각의 자리가 2개의 경우의 수를 가지는 MBTI의 경우 총 16가지의 경우의 수를 가지므로, 17명의 사람이 모이면 어떤 MBTI가 중복인지는 몰라도 무조건 하나의 MBTI는 같은걸 가지고 있는 사람이 있을 수 밖에 없다고 생각할 수 있다.
즉, 17명의 사람들 중 ENTJ가 17명일 수도 있고, ENTJ를 포함한 서로 다른 MBTI 16명과 그들 중 반드시 하나는 같은 MBTI를 가지는 한 사람이 있을 수도 있다는 것이다. 어떤 MBTI가 겹쳤는지는 모르겠지만, 어쨌든 겹쳤다는건 확실히 알 수 있겠지?
문제의 경우 3명의 MBTI를 확인해서 서로 가장 가까운 세 명의 MBTI를 고르면 되는데, 16명을 넘었을 때 반드시 2명은 겹친다는 논리를 확장해서 32명을 넘으면 반드시 3명은 겹친다고 할 수 있겠다.
이해가 잘 안된다면 MBTI 팻말이 붙은 비둘기 집에 한 사람씩 집어 넣어보면 된다. 처음 16명까지는 각자 혼자 집을 쓸 수 있겠지만, 17명이 되는 순간 최소 한 집에는 두 명의 사람이 들어간다. (물론 처음 들어가는 2명이 MBTI가 같았으면 처음부터 2명이 들어가 있을 수도 있다!)
여기서 확장해서, 같은 MBTI를 가지는 사람이 딱 2명씩만 있는 32명이 비둘기 집에 고르게 들어가 있을 때, 33번째 사람은 어떤 MBTI를 가지고 있든 반드시 들어가는 집의 인원이 3명이 되게 만든다. 쉽지 않나?!
적용
그럼 위의 알고리즘을 아래와 같이 개선할 수 있다.
def solution(students: List[str]):
if len(students) > 32:
return 0
ret = inf
for s1, s2, s3 in combinations(students, 3):
ret = min(ret, get_distance_of_3(s1, s2, s3))
return ret맨 앞에 위에서 설명한 논리를 그대로 옮겨서, 학생 수가 32명을 넘는 경우 반드시 3명의 학생은 같은 MBTI를 가지는 것이므로 세 학생이 서로 가지는 거리의 합은 무조건 0임을 의미한다.
느낀 점
요즘 BFS, DFS, DP, 그리디처럼 어느정도 문제를 해결하는 구조와 패턴이 명확한 문제를 많이 풀고 있었다. 그래서 그런지 이런 식으로 어느정도 수학적인 사고력이 필요한 문제를 만나니까 이때까지 그랬던 것처럼 구조적으로만 문제를 해결하려고 들었던 것 같다. 규칙성도 좋지만 엣지 케이스먼저 고려할 수 있도록,, 노력을 많이 해야 할 것 같다.
