가장 많이 받은 선물(프로그래머스) 문제풀이
문제
https://school.programmers.co.kr/learn/courses/30/lessons/258712
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 접근 방식
사람들의 이름과 이번 달 선물 기록이 주어지고, 해당 기록을 통해 아래 기준에 따라 다음 달에 선물을 가장 많이 받는 사람을 구하는 문제이다.
1. 두 사람이 선물을 주고 받았다면 이번달에 많이 준 사람이 다음 달에 선물을 받는다.
2. 주고 받은 기록이 없거나 같다면 (선물 지수)가 큰 사람이 작은 사람에게 선물을 하나 받는다.
* (선물 지수) = (선물을 준 횟수) - (선물을 받은 횟수)
위와 같은 조건을 기준으로 다음 달에 선물을 가장 많이 받은 사람을 구하기 위해서는 [두 사람간 선물 기록]을 저장하는 자료구조 1개와 [각 사람들의 선물 지수]를 저장해놓는 자료구조를 1개 두어서 저장해놓아야한다. 문제에서 각 사람을 식별하는 기준은 번호가 아닌 이름이기 때문에 아래와 같이 Map을 사용하여 [이름 -> 번호] 로 변환하고, 내부에서는 번호를 활용하여 문제를 풀었다.
# map 자료 구조 : {이름 : 번호}
# {"라이언": 2} 이렇게 저장하여, 이름 -> 번호 로 변환
friends_map=dict()
# 두 사람이 주고 받은 기록을 저장
# NxN 이차원 배열. [i번 사람]이 [j번 사람] 에게 [보낸 선물 횟수]를 저장한다.
histories=[[0 for _ in range(n)] for _ in range(n)]
# 사람들의 선물 지수를 저장
# gift_points[i] = i 번 사람의 선물 지수
gift_points=[0]*n
문제에서 사람들의 이름이 담긴 friends와 선물 기록인 gifts가 주어진다. 우선, friends를 순회하면서 map 자료구조에 {"이름" : 번호} 쌍을 넣어주고, gitfs를 순회하면서 [선물을 보낸 횟수를 저장하는 histories] 와 [선물 지수를 저장하는 gift_points]를 갱신한다.
# map 초기화, {"이름":번호}
for i in range(n):
friends_map[friends[i]]=i
for gift in gifts:
giver,taker=gift.split(" ")
# [이름->번호]로 변환
g_num=friends_map[giver]
t_num=friends_map[taker]
# 보낸 횟수 & 선물지수 갱신
histories[g_num][t_num]+=1
gift_points[g_num]+=1
gift_points[t_num]-=1
모든 histories와 gitf_points를 기록하였다면, 모든 사람들을 순회하면서 histories 및 gift_points를 확인하여 각 사람이 다음달에 받는 선물의 개수를 기록하고 그 중 최댓값을 반환한다.
시간 복잡도
gift 를 순회해야하기 때문에 gifs의 길이 M 에 대해 O(M) 이 걸리고, 두 사람을 선택하면서 비교할 때 이중 for문을 돌아야하기 때문에 사람 수 N에 대해 O(N^2) 이 걸린다. M과 N의 최댓값이 각 1e4, 50 이므로 시간 내에 동작한다.
코드
def solution(friends, gifts):
n = len(friends)
next_gifts = [0] * n
# map 자료 구조 : {이름 : 번호}
# {"라이언": 2} 이렇게 저장하여, 이름 -> 번호 로 변환
friends_map = dict()
# 두 사람이 주고 받은 기록을 저장
# NxN 이차원 배열. [i번 사람]이 [j번 사람] 에게 [보낸 선물 횟수]를 저장한다.
histories = [[0 for _ in range(n)] for _ in range(n)]
# 사람들의 선물 지수를 저장
# gift_points[i] = i 번 사람의 선물 지수
gift_points = [0] * n
# map 초기화, {"이름":번호}
for i in range(n):
friends_map[friends[i]] = i
for gift in gifts:
giver, taker = gift.split(" ")
# [이름->번호]로 변환
g_num = friends_map[giver]
t_num = friends_map[taker]
# 보낸 횟수 & 선물 지수 갱신
histories[g_num][t_num] += 1
gift_points[g_num] += 1
gift_points[t_num] -= 1
for i in range(n):
for j in range(i + 1, n):
# i, j 중 많이 준 사람 -> 다음 달 선물 개수 +1
if histories[i][j] > histories[j][i]:
next_gifts[i] += 1
elif histories[i][j] < histories[j][i]:
next_gifts[j] += 1
# 주고 받은게 같다면 선물 지수 비교해서 높은 사람 +1
elif gift_points[i] > gift_points[j]:
next_gifts[i] += 1
elif gift_points[i] < gift_points[j]:
next_gifts[j] += 1
answer = max(next_gifts)
return answer
회고
이름이 주어졌을 때 이를 쉽게 관리 및 처리하기 위해 map을 사용하여 번호로 변환하였다. 카카오의 경우 식별자가 문자열로 나오는 경우가 많은 것으로 아는데 비슷한 문제가 나오는 경우 map을 사용하여 [이름 > 번호] 로 맵핑하도록 하자