백준 #20529 - [S1] 가장 가까운 세 사람의 심리적 거리 : 비둘기집원리

(python3)

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

 

이 문제 재밌네요!! 비둘기집 원리가 매우 간단한 이론이지만 재밌는 상황을 많이 만들어내는 것 같아요.

 

비둘기집 원리

비둘기집 원리란, "5칸짜리 집에 비둘기 6마리가 살려면 최소 한칸은 2마리 이상 살아야한다."

저는 16개의 mbti 를 2진법처럼 다뤄서 배열의 index 로 만들어서 사용했습니다. 잡다한 작업들이 많습니다.

다른 분의 코드를 보니 훨씬 깔끔한 코딩이 가능하더라구요..!!

일단 제 코드부터 소개하자면

 

코드

import sys
def solution(input) :
	# 16개의 mbti
    MBTI = ['ISTJ', 'ISFJ', 'INFJ', 'INTJ', 'ISTP', 'ISFP', 'INFP', 'INTP', 'ESTP', 'ESFP', 'ENFP', 'ENTP', 'ESTJ', 'ESFJ', 'ENFJ', 'ENTJ']
    # 2개의 mbti 사이 거리를 미리 계산해두기
    dist_map = [[0 for _ in range(16)] for _ in range(16)]
	
    # dist_map 채우기
    def make_dist_map() : # 모든 조합에 대해 거리 계산, [a][b] 와 [b][a] 가 같으므로 한번만 계산
        for i1 in range(16) :
            m1 = MBTI[i1]
            n1 = mbti_to_idx(m1)
            for i2 in range(i1,16) :
                m2 = MBTI[i2]
                n2 = mbti_to_idx(m2)
                dist = 0
                for l1,l2 in zip(m1,m2) :
                    if l1 != l2 : dist += 1
                dist_map[n1][n2] = dist
                dist_map[n2][n1] = dist

	# mbti 를 2진법화해서 0~15의 값으로 치환
    def mbti_to_idx(mbti) :
        idx = 0
        if mbti[0] == 'I' : idx+=8
        if mbti[1] == 'N' : idx+=4
        if mbti[2] == 'T' : idx+=2
        if mbti[3] == 'P' : idx+=1
        return idx
    
    def cal_dist() :
        mbti_cnt = [0]*16
        N = int(input().strip())
        mbtis = input().split()
        for m in mbtis :
            i = mbti_to_idx(m)
            mbti_cnt[i] += 1
            if mbti_cnt[i] >= 3 : # 같은 mbti가 3개 이상 있으면 최소 거리가 0. 비둘기집 원리 처리 (일종의..)
                return 0
        # idx들의 배열로 변환
        idxs = []
        for i in range(16) :
            n = mbti_cnt[i]
            for _ in range(n) :
                idxs.append(i)
        # 모든 3개 조합에 대해 거리 계산
        dists = []
        for i in range(len(idxs)) :
            mi = idxs[i]
            for j in range(i+1,len(idxs)) :
                mj = idxs[j]
                for k in range(j+1,len(idxs)) :
                    mk = idxs[k]
                    d = 0
                    d+=dist_map[mi][mj]
                    d+=dist_map[mj][mk]
                    d+=dist_map[mk][mi]
                    dists.append(d)
        return min(dists) # 최단 거리 리턴
        

    make_dist_map()
    
    T = int(input().strip())
    for _ in range(T) :
        print(cal_dist())

input = sys.stdin.readline
solution(input)

 

 

최단 시간 코드 분석

코드 출처 : https://www.acmicpc.net/source/61721505

import sys

def input(): # 한문장씩 strip 한걸 받아오는 함수를 따로 만들어서 쓰시네요 편한 방법인듯!
    return sys.stdin.readline().strip()

# ==================================================================================

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(input().split(' '))

    if n > 32: # 찐 비둘기집 원리. 하나의 mbti가 3번 이상 나오면 최단거리가 0이 되고,
    		   # 16개의 mbti 가 2번씩 나오면 32. 33개부턴 무조건 3번 이상 나오는 mbti 가 존재한다. 
        print(0)

    else:
        mbti = dict() # dict key = mbti str, value = 등장횟수
        for i in arr:
            if i not in mbti:
                mbti[i] = 1
            else:
                mbti[i] += 1

        if max(mbti.values()) > 2: # 하나의 mbti가 3번 이상 나오면 최단거리 0
            print(0)
        else:
            min_dist = 8
            flag = False
            for a in range(n-2):
                for b in range(a+1, n-1):
                    for c in range(b+1, n): # 모든 3가지 조합에 대해
                        tmp = 0
                        for j in range(4): # mbti 한단어씩 살폈을때 경우의수는 2가지.
                            if arr[a][j] == arr[b][j] and arr[a][j] == arr[c][j]: # 셋 다 같거나
                                pass
                            else: # 하나만 다르거나. 하나만 다르면 거리는 2가 증가한다.
                                tmp += 2 

                        min_dist = min(min_dist, tmp)
                        if min_dist == 2: # 0이 아닌 경우 최단 거리는 2. 2가 등장 즉시 종료
                            flag = True
                        if flag:
                            break
                    if flag:
                        break
                if flag:
                    break
            print(min_dist)

 

my solved.ac :

solved.ac