프로그래머스 Lv.1: 가장 많이 받은 선물 - Python 풀이

문제 설명

https://school.programmers.co.kr/learn/challenges?order=recent&partIds=58464

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

프로그래머스

 

2024 KAKAO WINTER INTERNSHIP에서 제일 난이도가 낮은 '가장 많이 받은 선물'을 풀어보았다.

 

• 입력: 친구들 이름이 저장되어 있는 str 배열 friends, 과거 주고받은 선물 내역이 저장되어 있는 str 배열 gifts
  • gifts 배열의 원소는 "muzi frodo" 이런 형태로 공백의 앞에 위치한 값이 선물을 준 친구이고, 공백의 뒤에 위치한 값이 선물을 받은 친구이다.
• 반환: 다음 달에 선물을 가장 많이 받을 친구의 선물 개수

다음 달에 선물을 주고받을 때 아래와 같은 규칙을 따른다.

• 두 사람이 선물을 주고받은 기록이 있다면, 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받는다.
• 두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물을 하나 받는다.
  • 이 때, 선물 지수란 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값이다.
  • 두 사람의 선물 지수도 같다면, 다음 달에 선물을 주고받지 않는다.

 

풀이 과정

우선 규칙을 확인하여 다음 달에 각 친구들이 받을 선물의 개수를 구하고, 그 중 최댓값을 출력해야 겠다고 생각했다.

그러기 위해서는 가능한 모든 관계 사이의 주고받음을 기록해야 한다. 선물 지수의 경우 주고받은 기록이 없거나 같을 때가 생기면 구하려 했다.

def solution(friends, gifts):
    # 주고받은 선물 내역을 저장할 2차원 배열을 사람수 * 사람수의 크기로 생성
    gifts_records = [[0] * len(friends) for _ in range(len(friends))]
    # 사람 이름과 friends 배열에서의 인덱스를 저장할 딕셔너리 생성
    friends_dict = {}
	
    # 딕셔너리 값 채우기
    for i, name in enumerate(friends):
        friends_dict[name] = i

	# 선물 내역 돌면서 gifts_records 값 채우기
    for g in gifts:
    	# 공백으로 구분되어 있는 g를 split
        gift = g.split()
        # 딕셔너리를 통해 선물 준 사람의 index 구하기
        sender_index = friends_dict[gift[0]]
        # 딕셔너리를 통해 선물 받은 사람의 index 구하기
        receiver_index = friends_dict[gift[1]]
        # gifts_records에 값 업데이트
        gifts_records[sender_index][receiver_index] += 1
        
    # 다음 달에 받을 선물 개수를 저장할 배열을 사람수의 크기로 생성
    next_gifts = [0] * len(friends)
    
    # 이중 for문을 통해 모든 관계성의 주고받음을 확인
    for i in range(len(friends)):
        for j in range(i+1, len(friends)):
        	# 인덱스 i가 준 게 인덱스 j가 준 것보다 많으면
            if gifts_records[i][j] > gifts_records[j][i]:
            	# 다음 달에 i가 선물 1개 받음
                next_gifts[i] += 1
            # j가 준 게 더 많으면
            elif gifts_records[i][j] < gifts_records[j][i]:
            	# 다음 달에 j가 선물 1개 받음
                next_gifts[j] += 1
            # 똑같이 줬으면 (서로 주고받은 게 없는 경우도 여기에 해당)
            else:
            	# i가 준 선물의 개수
                # 특정 row에 해당하는 col 값을 모두 더하여 계산
                i_send_score = sum(gifts_records[i])
                # i가 받은 개수
                # 특정 col에 해당하는 row 값을 for문을 통해 모두 더하여 계산
                i_receive_score = 0
                for g in gifts_records:
                    i_receive_score += g[i]
                # i의 선물 지수 계산
                i_score = i_send_score - i_receive_score
                # j가 준 선물의 개수
                j_send_score = sum(gifts_records[j])
                # j가 받은 선물의 개수
                j_receive_score = 0
                for g in gifts_records:
                    j_receive_score += g[j]
                # j의 선물 지수 계산
                j_score = j_send_score - j_receive_score
                # 둘의 선물 지수 대소비교를 통해 다음 달에 받을 선물 수 업데이트
                if i_score > j_score:
                    next_gifts[i] += 1
                elif i_score < j_score:
                    next_gifts[j] += 1

    # 각 사람이 다음 달에 받을 선물의 개수 중 최댓값을 반환
    return max(next_gifts)

내 생각에 풀이에 핵심이 되는 포인트는 friends_dict를 도입한 부분이다.

이 예시의 표처럼 2차원 배열(gifts_records)에 주고받은 기록을 저장해두고 확인해야 겠다고 생각했다. 그러나 이 표를 만드는 과정에서 gifts를 하나씩 돌면서 gift[0]은 준 사람, gift[1]은 받은 사람의 '이름(str)'이 주어지는데, 사람 수 * 사람 수한 만큼 0으로 초기화 해둔 gifts_records에 애들 이름이 적혀 있는 것도 아니고... 이걸로 어떻게 gifts_records 값을 채우지?

 

-> 2차원 배열인 gifts_records는 friends의 인덱스 값을 그대로 따라서 인덱스를 통해 사람을 구별하기 때문에 gift[0]과 gift[1]의 각 사람이 friends에서 몇 번째 인덱스였는지 알아야 한다.

-> 값을 넣으면 인덱스가 뿅 나와야...

=> Key를 통해 Value 값을 얻을 수 있는 딕셔너리 구조가 생각났다.

 

이름 값을 가지고 인덱스를 구하고자 하기 때문에 Key를 이름으로 두고, Value를 인덱스로 두었다.

 

그 후의 코드는 그냥 규칙을 보며 그대로 코드로 구현했다.

이중 for문의 else 문이 '선물 지수' 까지 확인해야 하는 경우라서 저 안에서 선물 지수 값을 i꺼, j꺼 각각 구했는데, 내가 '받은' 선물의 개수를 구해야 할 때에 2차원 배열의 특정 column 값을 전부 더해야 해서 for문을 또 써야 했다. 이중 for문 안에 또 for문...? 이거 괜찮으려나 틀리면 다시 하지 뭐 ^ㅡ^ 하고 냈는데 정답.

i와 j는 friends 배열의 길이에 달렸고 g는 gift_records의 길이에 달렸는데, gift_records의 크기는 사람 수 * 사람 수라서 이것도 결국 friends 배열의 길이에 달렸다. 문제의 조건을 보면 2 ≤ friends의 길이 = 친구들의 수 ≤ 50 로, 최대여도 50이라 시간복잡도가 괜찮았던 것 같다.

 

12시 전에 풀어서 다행~