[프로그래머스/python] 2024 KAKAO WINTER INTERNSHIP가장 많이 받은 선물

문제: https://school.programmers.co.kr/learn/courses/30/lessons/258712

프로그래머스

 

 

사용알고리즘: 없음 -> 구현

 

 

카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있다. 이번 달까지 선물을 주고 받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 한다. 

 

 

규칙

• 두 사람이 선물을 주고 받은 기록이 있는 경우, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 받음
• 두 사람이 선물을 주고 받은 기록이 하나도 없거나 주고 받은 수가 같은 경우, 선물지수가 더 작은 사람이 선물지수가 더 큰 사람에게 선물을 줌

 

입력으로 친구들의 이름을 담은 1차원 문자열 배열 friends 와 이번 달까지 친구들이 주고 받은 선물 기록을 담은 1차원 문자열 배열 gifts 가 매개변수로 주어짐.

 

 

먼저 서로 주고 받은 선물의 개수를 알기 위해 gifts 배열을 이용해 선물을 주고 받은 history 를 기록한다. 사진과 같이 기록을 정리하기 위해 아래와 같이 코드를 짜주었다. 

문제에 첨부되어 있는 표

friendsDict = {}
history = {}

# 돌면서 딕셔너리 초기화
for i in range(len(friends)):
    friendsDict[friends[i]] = i
    history[friends[i]] = [0] * len(friends)

# 선물 준 사람 받은 사람 기록하기
for i in range(len(gifts)):
    sender, receiver = gifts[i].split()
    history[sender][friendsDict[receiver]] += 1

 

- history 는 {이름: [ ], 이름: [ ] ... } 형식으로 이름 별로 선물 준 기록을 정리하기 위해 딕셔너리를 사용

- friendsDict 는 {이름: index, 이름: index ... } 형식으로 는 for 문을 돌면서 history 초기화 해주기 위해 사용

 

 

이제 history 를 돌면서 선물 준 횟수를 비교하면 된다. 

 

muji 가 선물 준 사람일 때 아래와 같이 비교를 하게 된다. (같은 형광펜 색이 칠해진 것끼리 비교하는 것)

- muji vs ryan

- muji vs frodo

- muji vs neo

 

차례가 돌면서 ryan 이 선물 준 사람이 되면 이미 앞에서 비교했던 muji vs ryan 을 한 번 더 비교하게 되는데, 비교할 필요가 없으므로 두 번째 for 문에서는 i 번째 인덱스부터 시작한다. 

(muji vs ryan 와 ryan vs muji 는 똑같다는 것을 생각하면 된다 -> 비교할 필요없다, 헛수고임)

 

선물지수는 선물을 주고 받은 기록이 없거나 같은 개수의 선물을 주고 받았을 경우에만 비교하면 되므로, 미리 계산해놓지 않고 기록이 없거나 개수가 같은 경우에 계산하도록 코드를 짰다. 

(nextMonthGift 는 다음 달에 선물 받을 개수가 적힌 리스트이다.)

for i in range(len(friends)):
    for j in range(i, len(friends)):
        if history[friends[i]][j] > history[friends[j]][i]: # i 가 더 큼
            nextMonthGift[i] += 1
        elif history[friends[i]][j] < history[friends[j]][i]: # j 가 더 큼
            nextMonthGift[j] += 1
        else: # 선물을 주고 받은 기록이 없거나 서로 같은 개수의 선물을 주고 받음
            sendPointX, receivePointX = sum(history[friends[i]]), 0
            sendPointY, receivePointY = sum(history[friends[j]]), 0

            # 돌면서 선물지수 계산
            for k in range(len(friends)):
                receivePointX += history[friends[k]][i]
                receivePointY += history[friends[k]][j]
            if (sendPointX - receivePointX) > (sendPointY - receivePointY): # 왼쪽 > 오른쪽
                nextMonthGift[i] += 1
            elif (sendPointX - receivePointX) < (sendPointY - receivePointY): # 왼쪽 < 오른쪽
                nextMonthGift[j] += 1

 

 

완성코드

def solution(friends, gifts):
    friendsDict = {}
    history = {}
    nextMonthGift = [0] * len(friends)

    # 돌면서 딕셔너리 초기화
    for i in range(len(friends)):
        friendsDict[friends[i]] = i
        history[friends[i]] = [0] * len(friends)

    # 선물 준 사람 받은 사람 기록하기
    for i in range(len(gifts)):
        sender, receiver = gifts[i].split()
        history[sender][friendsDict[receiver]] += 1

    for i in range(len(friends)):
        for j in range(i, len(friends)):
            if history[friends[i]][j] > history[friends[j]][i]: # i 가 더 큼
                nextMonthGift[i] += 1
            elif history[friends[i]][j] < history[friends[j]][i]: # j 가 더 큼
                nextMonthGift[j] += 1
            else: # 선물을 주고 받은 기록이 없거나 서로 같은 개수의 선물을 주고 받음
                sendPointX, receivePointX = sum(history[friends[i]]), 0
                sendPointY, receivePointY = sum(history[friends[j]]), 0

                for k in range(len(friends)):
                    receivePointX += history[friends[k]][i]
                    receivePointY += history[friends[k]][j]
                if (sendPointX - receivePointX) > (sendPointY - receivePointY): # 왼쪽 > 오른쪽
                    nextMonthGift[i] += 1
                elif (sendPointX - receivePointX) < (sendPointY - receivePointY): # 왼쪽 < 오른쪽
                    nextMonthGift[j] += 1
    answer = max(nextMonthGift)
    return answer