2024 KAKAO WINTER INTERNSHIP > 가장 많이 받은 선물 - Python, 구현

 

https://school.programmers.co.kr/learn/courses/30/lessons/258712?language=python3

프로그래머스

 

코드

 

def solution(friends, gifts):
    size = len(friends)
    friends_idx = {name:i for i, name in enumerate(friends)}
    history = [[0] * size for _ in range(size)]
    gift_sub = [0] * size
    result = [0] * size
    
    for gift in gifts:
        A, B = gift.split(" ")
        history[friends_idx[A]][friends_idx[B]] += 1
    
    for i in range(size):
        give = sum(history[i])
        gived = sum(history[j][i] for j in range(size))        
        gift_sub[i] = give - gived
        
    for i in range(size):
        for j in range(i+1, size):
            if history[i][j] > history[j][i]:  # i가 더 많이 준 경우
                result[i] += 1
            elif history[i][j] < history[j][i]:  # j가 더 많이 준 경우
                result[j] += 1
            else:  # 주고받은 횟수가 같은 경우
                if gift_sub[i] > gift_sub[j]:
                    result[i] += 1
                elif gift_sub[i] < gift_sub[j]:
                    result[j] += 1
        
    return max(result)

 

난이도가 높다기보다는 좀 손이 가는 구현 문제였습니다.

 

풀이 방식이야 문제에서 설명하는 방법을 따라가기만 하면 됩니다.

 

선물 주고 받은거 기록 -> 선물 지표 구하기 -> 위의 두개를 바탕으로 다음달 받을 선물 개수 구하기

 

0. 준비

 

딕셔너리로 사람들의 이름별 인덱스를 기록해줍니다.

 

1. 선물 주고 받은거 기록

 

gits의 이력을 바탕으로

 

history[준 사람][받은 사람]에 +1 해주면서 주고 받은 선물 개수를 구합니다.

 

2. 선물 지표 구하기

 

 

반복문을 돌려 구합니다.

 

3. 다음달 받을 선물 개수 구하기

 

분기가 3개로 나눠집니다.

 

선물을 준 사람이 A, 받은 사람이 B일 때

 

1. A가 더 많이 줬는지

2. B가 더 많이 줬는지

3. 둘 다 같은지 or 주고 받지 않았는지

 

이를 조건문으로 표시하면

 

if history[i][j] > history[j][i]:  # i가 더 많이 준 경우
	result[i] += 1
elif history[i][j] < history[j][i]:  # j가 더 많이 준 경우
	result[j] += 1
else:  # 주고받은 횟수가 같은 경우
	if gift_sub[i] > gift_sub[j]:
		result[i] += 1
	elif gift_sub[i] < gift_sub[j]:
		result[j] += 1

 

이렇게 됩니다.

 

그런데 3은 주고 받은 횟수가 같은 것만 체크 하는거 아님?

 

안 주고 받은거는??

 

할 수 있는데

 

안 주고 받은 거는 둘 다 선물 개수가 0으로 같습니다.

 

돌아가서

 

이 뒤로는

 

1, 2의 경우는 누가 더 주냐에 따라 선물을 누가 받을지 알 수있고

 

3의 경우는 선물 지표를 확인 하면 됩니다.

 

그 후 result의 최댓값을 구하면 정답이 나오는 겁니다.

 

그리고

 

선물 주고 받은 기록과 지표를 한 번에 계산해도 됩니다.

 

def solution(friends, gifts):
    size = len(friends)
    friends_idx = {name: i for i, name in enumerate(friends)}
    history = [[0] * size for _ in range(size)]
    gift_sub = [0] * size
    result = [0] * size

    # 선물 기록 및 선물 지수 계산
    for gift in gifts:
        A, B = gift.split()
        giver, receiver = friends_idx[A], friends_idx[B]
        history[giver][receiver] += 1
        gift_sub[giver] += 1  # 준 선물
        gift_sub[receiver] -= 1  # 받은 선물

    for i in range(size):
        for j in range(i + 1, size):
            if history[i][j] > history[j][i]:
                result[i] += 1
            elif history[i][j] < history[j][i]:
                result[j] += 1
            else:  # 같으면 선물 지수 비교
                if gift_sub[i] > gift_sub[j]:
                    result[i] += 1
                elif gift_sub[i] < gift_sub[j]:
                    result[j] += 1

    return max(result)

 

성능은 큰 차이가 없을 겁니다.

 

전 구현은 차근 차근 푸는 걸 선호하지만

 

여러분의 취향에 따라

 

골라 잡수시면 됩니다.

 

 

다음에 또 봐요