[파이썬/Python] 프로그래머스 : 가장 많이 받은 선물

숨·2024년 12월 12일

알고리즘 문제 풀이

목록 보기

90/105

📌 문제 : 프로그래머스 - 가장 많이 받은 선물

📌 문제 탐색하기

friends : 친구의 이름 (2 ≤ len(friends) ≤ 50)
gifts : 선물 주고 받은 정보 (1 ≤ len(gifts) ≤ 10,000)
A : 선물 준 사람
B : 선물 받은 사람

✅ 입력 조건
1. 친구 이름 저장된 리스트 입력
2. A B 형식으로 gifts 정보 입력
✅ 출력 조건
1. 가장 많이 받아야 할 친구의 선물 개수 출력

총 2가지의 연산이 필요하다
1. 선물지수 연산
2. 받을 선물의 수 연산

각 연산의 결과를 저장하기 위해 1차원 리스트, 2차원 리스트를 정의한다.
for문을 통해 입력받은 gifts와 주고 받은 결과를 저장하기 위해 정의한 gift_map에 접근한다.
for문을 돌면서 선물 주고 받은 횟수, 선물지수를 한번에 계산해서 여러번 for문을 돌리는 것을 피한다.

친구들 각각의 받을 선물 수를 계산하기 위해 gift_map을 접근해서 비교 연산을 진행한다.
최종적으로 최대 선물의 수를 구하기 위해 max() 연산으로 원하는 정답을 return한다.

가능한 시간복잡도

선물 주고 받은 내역 저장 → $O(len(friends)^2)$
선물 주고 받은 횟수 계산 → $O(len(gitfts) * len(friends))$
최대 선물 수 출력 → $O(len(friends))$

최종 시간복잡도
$O(len(gifts) * len(friends) + len(friends)^2)$ 가 되는데,
최악의 경우 $O(10,000 * 50 + 5^2) = O(500,000)$ 이 된다.

알고리즘 선택

for문으로 반복하며 선물 개수 계산

📌 코드 설계하기

친구들 수 정의
받을 선물 수 저장할 리스트 초기화
선물 주고 받은 내역 저장할 맵 정의
선물지수 저장 변수 정의
선물 주고 받은 횟수 계산
5-1. 주고 받은 사람 분리
5-2. 인덱스 접근
5-3. 주고 받은 횟수 저장
맵에 접근해 받을 선물 계산
6-1. i가 준 횟수가 더 많으면 i가 받을 선물의 수 증가
6-2. j가 준 횟수가 더 많으면 j가 받을 선물의 수 증가
6-3. 횟수가 없거나 같다면 선물지수 비교해 선물의 수 증가
받을 선물의 최댓값 출력

📌 시도 회차 수정 사항

1회차

[원래 아이디어]
1. friends로 딕셔너리 만들어서 [0, 0, 0]으로 초기화
2. gifts에 접근해서 인덱스 0에 있는 사람의 딕셔너리의 인덱스 0에 +1, 인덱스 1에 있는 사람의 딕셔너리의 인덱스 1에 +1
3. 모두 계산 후 딕셔너리에 접근해 인덱스 2의 값을 선물지수 계산한 값으로 갱신
4.  딕셔너리에 접근해서 값 하나씩 비교하면서 받을 선물 수 계산하고 둘 중 큰 값으로 갱신

처음엔 딕셔너리를 만들어 풀려고 했었다.
- key → friends
- values → [0, 0, 0]으로 정의 (0: 준 횟수, 1: 받은 횟수, 2: 선물지수)
위와 같이 정의하니 어떤 사람과 선물을 주고 받아야 하는지 저장하는 과정이 빠져있었다. 이 부분을 어떻게 해야하나 고민하다가 해결하지 못해서 참고 코드를 활용하게 되었다.

📌 정답 코드

def solution(friends, gifts):
    # 친구들 수 정의
    n = len(friends)
    
    # 받을 선물 수 저장할 리스트 초기화
    answer = [0] * n
    
    # 선물 주고 받은 내역 저장할 맵 정의
    gift_map = [[0] * n for _ in range(n)]
    
    # 선물지수 저장 변수 정의
    gift_index = [0] * n
    
    # 선물 주고 받은 횟수 계산
    for gift in gifts:
        # 주고 받은 사람 분리
        A, B = gift.split()
        # 인덱스 접근
        give_idx, take_idx = friends.index(A), friends.index(B)
        # 선물지수 계산
        gift_index[give_idx] += 1
        gift_index[take_idx] -= 1
        # 주고 받은 횟수 저장
        gift_map[give_idx][take_idx] += 1

    # 맵에 접근해 받을 선물 계산
    for i in range(n):
        for j in range(i+1, n):
            # i가 준 횟수가 더 많으면?
            if gift_map[i][j] > gift_map[j][i]:
                answer[i] += 1
            # j가 준 횟수가 더 많으면?
            elif gift_map[i][j] < gift_map[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))

결과

📌 회고

각 이름과 짝짓는다고 생각해서 딕셔너리를 구현하고 선물지수 계산까지 진행했는데 가장 중요한 선물 주고 받은 내역 기록을 빼먹었다. 딕셔너리, 2차원 리스트 모두 정의하고 연산하기엔 연산량이 너무 많아지는 건 아닌가 하고 고민만 하다가 결국 도움을 받았다.
코드 완성도 하지 못했는데 효율성을 따지다가 코드를 마무리 짓지 못했다. 지레 겁먹고 진행해보지 않은 것이 많이 후회된다. 선 빡구현 후 수정 잊지 말아야겠다.