[백준 20529번] 가장 가까운 세 사람의 심리적 거리

문제 출처

문제 유형

• 수학
• 브루트포스 알고리즘
• 비둘기집 원리

풀이

해당 문제는 solved.ac 사이트 기준 실버 1 문제입니다.

N개의 문자열들 가운데, 각각의 문자열들의 차이가 가장 적은 3개의 문자열을 찾아내는 문제입니다.

A,B,C 의 문자열이 있다고 했을 때,

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

그렇게 A,B,C 를 뽑아 심리적인 거리가 가장 적은 조합을 찾아 거리를 출력하면 됩니다. 이 문제는 문자열이 최대 100,000 개이기 때문에, 각각의 조합을 전부 찾게 되면 시간 복잡도가 어마어마하게 커집니다. 보통 100,000 x 100,000의 문제는 시간복잡도를 어떻게 해결하냐가 관건입니다.

이 문제에서는 비둘기집 원리를 사용하게 되는데, 특정 조건에 해당하는 타입의 개수가 n개인 어떠한 리스트가 있고, 그 리스트의 개수가 n+1이 되어버리면 리스트 안에는 같은 조건을 가진 임의의 변수가 최소한 두 개는 존재한다는 원리입니다. 어찌보면 당연하다고도 할 수 있는데, 실제로 처음 문제에 적용할 때는 잘 생각이 나지 않습니다.

풀이 코드

from itertools import combinations

# 문제 개수
count = int(input())

for _ in range(count):
    # 문자열 개수
    x = int(input())
    
    # 문자열 리스트
    case = input().split()

    if x >= 33:
        print(0)

    else:
        # 문자열 리스트 조합
        combi = list(combinations(case, 3))
        
        # 최대 수
        answer = 100000

        for x in combi:
            temp = 0
            # 세 개의 문자열의 조합
            for str1, str2 in combinations(x, 2):
                # 각 문자열의 문자들을 하나씩 비교
                for char1, char2 in zip(str1, str2):
                    # 문자가 틀릴 경우 숫자 증가
                    if char1 != char2:
                        temp += 1

            # 가장 작은 수
            if answer > temp:
                answer = temp

        print(answer)

해당 풀이에서는 조합 라이브러리인 itertools.combinations와 문자열의 각 문자들을 비교해줄 zip()을 사용했습니다.