[프로그래머스] 가장 많이 받은 선물 (Python, 2024 카카오 winter internship)

프로그래머스

 

---

 

☁️ 문제 설명

• 선물을 주고받은 기록으로 다음 달에 누가 선물을 많이 받을지 예측
• 두 사람이 선물을 주고받은 기록이 있으면, 더 많은 선물을 준 사람이 다음 달 선물 + 1
• 두 사람이 선물을 주고받은 기록이 없거나 주고받은 선물의 수가 같으면, `선물 지수`가 더 큰 사람이 `선물 지수`가 더 작은 사람에게 선물 + 1
• `선물 지수` = 친구들에게 준 선물 - 받은 선물

 

☁️ 입출력

• 입력: `friends`, `gifts`
  • friends 예시: ["muzi", "ryan", "frodo", "neo"]
  • gifts 예시: ["muzi frodo", "muzi frodo", "ryan muzi"]
• 출력: 다음 달에 가장 많은 선물을 받는 친구가 받을 선물의 수(`answer`)

 

☁️ 제한 사항

• 2 <= friends 길이 = 친구들의 수 <= 50
  • friends 원소는 친구들의 이름으로 알파벳 소문자 이름들로 이뤄져 있고, 길이는 10 이하인 문자열
  • 동명이인X
• 1 <= gifts의 길이 <= 10,000
  • gifts 원소는 `"A B"` 형태의 문자열
  • A는 선물을 준 친구의 이름(`giver`), B는 선물을 받은 친구의 이름(`receiver`)
  • A와 B는 friends의 원소이며, A와 B가 같은 경우는 X

 

---

💡 문제 풀이 아이디어

• 구현 문제
• 입출력 예시로 제시한 표를 완성하기 (`board`, `gift_index`)
  • `board`: 주고받은 선물의 개수를 저장하는 2차원 배열
  • `gift_index`: 각 친구의 선물 지수를 저장하는 1차원 배열

• 문제에서 제시한 조건에 맞게 다음 달 받을 선물 개수를 answer(1차원 배열)에 저장하기

 

🚨 주의할 점

• `friends` 배열의 순서를 그대로 index화해서 `board` 배열에서 사용

---

 

💻 코드

def solution(friends, gifts):
    n = len(friends)
    answer = [0] * n
    
    board = [[0 for _ in range(n)] for _ in range(n)]
    gift_index = [0] * n
    
    # board, gift_index 만들기
    for gift in gifts:
    	giver, receiver = gift.split(" ")
        giver_index = friends.index(giver)
        receiver_index = friends.index(receiver)
        
        gift_index[giver_index] += 1
        gift_index[receiver_index] -= 1
        board[giver_index][receiver_index] += 1
     
     # 다음 달 받을 선물 개수 계산
     for i in range(n):
     	for j in range(i+1, n):
            if board[i][j] > board[j][i]:
                answer[i] += 1
            elif board[i][j] < board[j][i]:
                answer[j] += 1
            else:
                if gift_index[i] > gift_index[j]:
                    answer[i] += 1
                elif gift_index[i] < gift_index[j]:
                    answer[j] += 1
 
     return max(answer)

 

 

• 시간 복잡도
  • 첫 번째 for문
    • gifts 길이 : m
    • `index` 함수: O(n) * 2 = 2O(n) = O(n)
    • => O(m*n)
  • 두 번째 for문
    • O(n(n-1)/2) = O(n²)
  • 총: O(mn) + O(n²) = O(n²)