가장 많이 받은 선물(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

사람들의 이름과 이번 달 선물 기록이 주어지고, 해당 기록을 통해 아래 기준에 따라 다음 달에 선물을 가장 많이 받는 사람을 구하는 문제이다.

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을 사용하여 [이름 > 번호] 로 맵핑하도록 하자