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

20529번: 가장 가까운 세 사람의 심리적 거리

전형적인 문제는 쉽지만 아... 이걸 어떻게 풀어야 하지? 하는 문제이다.

A와 B 사이의 심리적인 거리는 zip 함수를 사용하면 쉽게 풀 수 있다.

근데 N명의 입력이 주어질 때, 가장 가까운 세 명의 학생? 이게 시간이 되나?

심지어 알고리즘 분류에는 비둘기 집의 원리가 있다.

아니... 보안에서나 보던 비둘기 집의 원리를 어떻게 활용해야 하지 이 코드에서?

우선 직접 짜보자. 짜보지도 않고 모르겠다고 하는 건 말도 안 되니까.

 

# ---------- Function ----------
def distance(A: str, B: str) -> int:
    cnt = 0
    
    for v1, v2 in zip(A, B):
        if v1 != v2: cnt += 1
            
    return cnt

우선 거리를 재는 distance() 함수부터 작성했다.

A와 B를 받아 zip으로 묶어준다. 예를 들어서 TEST와 TEXT를 각각 넣어주었다고 해보자.

zip 객체를 list로 바꾼다면, [('T', 'T'), ('E', 'E'), ('S', 'X'), ('T', 'T)]의 형태로 반환한다.

v1, v2로 unpacking하여 다른지 비교하여 cnt에 값을 더해준다.

 

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Main ----------
caseT = int(input())

for _ in range(caseT):
    people = int(input())
    MBTI = {}
    
    # dictionary: key(MBTI)-value(count)
    for v in list(input().rstrip().split()):
        MBTI[v] = MBTI.get(v, 0) + 1

입력이 들어왔을 때, 심리적 거리가 최소인 경우(0)는? 똑같은 게 3개 있을 때이다.

어떻게 표현할까 하다가, 다른 MBTI 입력 개수도 같이 세줄 겸 dict으로 구현했다.

이때 for문에서 입력을 직접 받아, key(MBTI) - value(개수)로 만들어주었다.

 

# ---------- Main ----------
# Checking max pigeonhole
MAX = max(MBTI.values())

# Is 0 difference
if MAX >= 3:
    print(0)

MAX 변수에 MBTI의 value들 중 가장 큰 값을 저장한다.

3 이상이라면 심리적인 거리는 0이니, 0을 출력하고 끝마친다.

 

# ---------- Import ----------
from itertools import combinations

# ---------- Main ----------
# Same things is exist
elif MAX == 2:
    gap = []
    for v1, v2 in combinations(MBTI.keys(), 2):
        gap.append(distance(v1, v2))

    print(min(gap) * 2)

만약 MAX가 2라면 ENFJ ENFJ ISTJ 이런 형태로 입력이 들어온 것이다.

그렇다면 ENFJ의 거리는 잴 필요가 없다. ENFJ와 ISTJ의 거리만 재면 되는 것이다.

입력받은 keys()들을 2개씩 combination하여 gap에 추가한다.

그 뒤 가장 작은 값에 2를 곱하면 된다.

2를 곱하는 이유는 두 명의 ENFJ와 한 명의 ISTJ이기 때문이다.

 

# ---------- Main ----------
# No duplicate
else:
    gap = []
    for v1, v2 in combinations(MBTI.keys(), 2):
        gap.append(distance(v1, v2))

    print(sum(sorted(gap)[:3]))

나머지 경우(else)는 중복하는 입력이 하나도 없는 경우이다.

MAX == 2인 경우와 코드가 거의 유사하다.

마찬가지로 keys()에서 2개씩 combination하여 차이를 조사한다.

그리고 gap을 정렬하여 가장 작은 3개의 값을 더하면 최솟값이 되리라 생각했다.

 

이렇게 코드를 작성하고 예제 입력을 테스트 해보았지만 틀렸다.

MAX >= 3인 부분에서는 틀릴 이유가 없으니 나머지 부분에서 틀렸으리라 생각했다.

실제로 계속해서 elif(MAX == 2)에서 오류가 나서 생각해보았다.

 

생각해보니 elif에서 치명적인 문제가 있었다.

중복하는 입력이 있다고 하더라도 그것의 심리적인 거리가 최소라는 보장은 없었다.

예를 들어서 ENFJ ENFJ ISTP ISTJ INTJ의 입력을 받았다고 해보자.

그럼 MBTI dictionary는 {'ENFJ': 2, 'ISTP': 1, 'ISTJ': 1, 'INTJ': 1}로 이루어질 것이다.

ENFJ-ISTP, ENFJ-ISTJ, ENFJ-INTJ, ISTP-ISTJ, ISTP-INTJ, ISTJ-INTJ 경우 중 가장 작은 차이를 고를 것이다.

 └ Combinations를 하면 생기는 6가지의 경우의 수이다.

즉 이말은 ENFJ와의 거리가 가장 작은 것을 고른다는 보장이 없다는 말이다.

 

문제는 더 있었다. 만약 위에서 ENFJ와의 거리가 가장 작은 걸 골랐다고 가정해보자.

그래도 과연 이게 최소 심리 거리를 보장받을 수 있을까? 아니다.

ISTP, ISTJ, INTJ 어느 것과도 ENFJ는 심리 거리가 3 이상이다. 그럼 최종 심리 거리는 6 이상이다.

하지만 ISTP, ISTJ, INTJ 셋 사이의 심리 거리는 1 + 1 + 2로 4에 불과하다.

MAX값이 2인 key가 최적의 해를 반환한다는 보장이 없다.

 

# ---------- Main ----------
# Is 0 difference
if MAX >= 3:
    print(0)

# Combinations all element, and sum min 3 side
else:
    gap = []
    for v1, v2 in combinations(MBTI.keys(), 2):
        gap.append(distance(v1, v2))

    print(sum(sorted(gap)[:3]))

결국 하나하나 비교하는 방법밖에 없었기에 elif 조건문은 지워버렸다.

elif일 때나 else일 때나 코드도 기본적으로 유사했기 때문에 상관이 없었다.

더 빠른 연산을 위해 MAX 값이 2일 때의 예외 처리를 해줬을 뿐이다.

 

그래도 여전히 틀렸습니다가 나온다. 결국 또 else 부분이 문제라는 거다.

곰곰이 생각해보니 저 코드도 말이 안 되는 코드였다.

최솟값에만 집중하다보니 세 MBTI와의 상관 관계를 무시해버렸다.

입력이 예를 들어서 ISFJ INFJ ESTP ESFP ENFJ ENTJ가 들어왔다고 가정해보자.

그럼 다양한 경우의 수들을 조합해서 그 차이를 계산할 것이다.

오름차순으로 정렬하면 ISFJ INFJ의 1, ESTP ESFP의 1, ENFJ ENTJ의 1이 가장 앞의 3개이다.

최솟값은 맞으나 세 명의 상관 관계가 전혀 아니다.

애초에 Combination을 할 때, 2가 아니라 3으로 진행했어야 한다.

 

# ---------- Main ----------
people = int(input())
MBTI = list(input().rstrip().split())

# Pigeonhole principle
if people > 32: print(0)

# Combinations all element, and sum min 3 side
else:
    gap = []
    for v1, v2, v3 in combinations(MBTI, 3):
        g1 = distance(v1, v2)
        g2 = distance(v1, v3)
        g3 = distance(v2, v3)
        gap.append(g1 + g2 + g3)

    print(min(gap))

코드에 크게 2가지 변화를 주었다.

하나는 요소들을 조합(Combination)하는 방법, 다른 하나는 비둘기 집 원리의 조건문이다.

 

우선 Combination부터 살펴보면, 위와 다르게 이제는 dict으로 저장할 필요가 없어졌다.

따라서 문자열을 list로 입력받고 3개씩 조합해주었다.

 └ 다른 언어에서는 3중 for문을 사용하면 된다. Python3에서는 3중 for문보다 combinations을 활용하면 더욱 빠르다.

v1, v2, v3로 unpacking해서 각각의 요소들의 거리를 측정해준다.

그리고 gap에 이 값들을 추가해주고, 최종적으로 가장 작은 값을 출력하면 된다.

지금 글을 쓰면서 생각난 건데, gap을 굳이 list로 받지 않았어도 됐겠다 싶다.

gap을 int로 선언하고, 들어올 때마다 더 작은 값을 gap에 넣어주면 메모리를 더 아낄 수 있었다.

 

비둘기 집 원리는 dict에서 list로 MBTI를 받음에 따라 조건에 변화를 줄 필요가 있었다.

문제를 해결할 때 언제나 최악의 경우를 생각해야 한다.

입력이 가장 중복하지 않게끔 들어온다면 몇 개가 와야 0을 출력할 수 있을까?

최악의 경우 32개(16개의 MBTI가 중복하지 않고 들어온다)가 들어오고 난 뒤이다.

그러고 나면 어떤 MBTI가 들어오든 무조건 3개가 중복되는 MBTI가 생기게 된다.

 └ 이래서 비둘기 집 원리가 알고리즘 분류에 있었구나 싶었다.

단순하게 개수 입력이 32개를 초과하면 0을 출력하면 되는 문제였다.

 

그렇게 정답을 맞췄다.

비둘기 집 원리에 따르면 32개가 최악의 경우라는 이야기이다.

그럼 최악에 32 * 32 * 32의 경우의 수인데, 이는 32,768개로 브루트포스가 4만 개도 돌지 않는다.

생각보다 그렇게 오래 걸리는 문제가 아니라는 거다.

어떤 문제든 우선 시도해보는 게 중요하다는 걸 다시끔 깨달았다.