코딩테스트 연습 Lv1 - 2024 Kakao Winter Intership 가장 많이 받은 선물

문제 설명

이 문제는 2024 카카오 윈터 인턴십 문제로 친구 리스트와 선물을 주고 받은 목록을 입력받아 특정 조건을 만족하여 다음달에 선물을 가장 많이 받는 친구의 선물 갯수를 반환하는 문제이다.

 

해결 방법

먼저 파이썬으로 이 문제를 해결하였으며 기본적인 해결 방식은 먼저 각 친구별로 선물 받거나 준 횟수를 2차원 리스트로 만들고 이 2차원 리스트를 가지고 각 친구마다 몇개의 선물을 주고 받았는지 계산하고 선물 지수 라는 값을 계산하여 다음 달에 선물을 받을 갯수를 구하는 방식으로 진행했다.

 

코드 설명

먼저 각 친구마다 선물을 주고 받은 갯수와 선물 지수를 구하기 위해 2차원 리스트를 만든다

    gift_mat = [[0 for _ in range(len(friends))] for _ in range(len(friends))]
    gift_rating=[[0 for _ in range(4)] for _ in range(len(friends))]
    #gift_mat=[[0]*len(friends)]]*len(friends)
    #gift_rating=[[0]*4]*len(friends)

 

처음에 2차원 리스트를 초기화하는 방식은 주석처리된 방식이였다. 그런데 해당 방식으로 진행하니 gift_mat에 값을 넣을때 모든 행에 값이 변경되어서 왜 그런지 알아보니 해당 방식으로 초기화를 하면 각 행이 모두 같은 리스트 객체를 참조하게 되기 때문에 하나의 행만 바꿔도 다른 행에서도 값이 변경되는 것이였다. 그런 이유로 각 행이 다른 리스트를 참조하게 만들기 위해서 위 방식으로 초기화를 하였다.

for j in range(0,len(gifts)):
        gift_from=gifts[j].split(" ")[0]
        from_index=friends.index(gift_from)
        gift_to=gifts[j].split(" ")[1]
        to_index=friends.index(gift_to)
        gift_mat[from_index][to_index]=gift_mat[from_index][to_index]+1

그런 다음 gifts 배열에서 선물을 받은 친구와 선물을 준 친구를 구분하여 gift_mat 2차원 리스트에서 각 친구별로 주고 받은 선물의 갯수를 관리하기 위해서 위에 있는 반복문을 실행하여 선물 주고받은 리스트를 만들었다.

 

#선물 지수 계산
    for index in range(0,len(friends)):
        gift_rating[index][0]=sum(gift_mat[index])
        gift_rating[index][1] = sum(np.array(gift_mat).T[index])
        gift_rating[index][2]=gift_rating[index][0]-gift_rating[index][1]

위에서만든 gift_mat 2차원 리스트를 가지고 각 친구마다 주고 받은 선물의 총 합을 구하고 준 선물의 갯수에서 받은 선물 갯수를 구하여 선물 지수라는 값을 구한다. 이 선물 지수라는 값은 나중에 누가 선물을 받을지 결정할때 사용되는 지수이다. 여기서 numpy를 사용하여 받은 선물의 갯수를 쉽게 구하였다.

 

#선물 받는 횟수 계산
    for i in range(0,len(gift_mat)):
        for j in range(0,len(gift_mat)):
            if i==j:
                continue
            elif gift_mat[i][j]>gift_mat[j][i]:
                gift_rating[i][3]=gift_rating[i][3]+1
            elif gift_mat[i][j]==gift_mat[j][i]:
                if gift_rating[i][2]>gift_rating[j][2]:
                    gift_rating[i][3]=gift_rating[i][3]+1
                    
    answer=int(max(np.array(gift_rating).T[3]))

이제 최종적으로 누가 선물을 몇개 받을지 계산하는 과정이다. 이중 반복문으로 gift_mat을 탐색하며 주고 받은 선물의 갯수를 비교하여 더 크면 본인이 받을 선물이 늘어나고 만약 주고 받은 선물의 갯수가 같거나 주고 받은 적이 없을때는 선물 지수를 비교하여 더 큰 쪽이 선물을 받는 과정을 거쳐서 최종적으로 선물을 받는 갯수를 구한다. 여기서 굳이 이중 반복문으로 gift_mat을 탐색한 이유는 i,j값을 이용하여 친구끼리 주고 받은 선물의 갯수를 구하기 쉽게하기 위해서이다. 예를 들어 친구1이 있고 친구2가 있을때 친구1이 친구2에게 준 선물의 갯수는 3개이고 친구2가 친구1에게 준 선물의 갯수는 2라고 하면 각 값의 위치가 2차원 리스트에서는 i와 j값을 바꾼 위치에 있기 때문이다.

그런 다음 아까 처럼 numpy를 이용하여 리스트의 행과 열을 바꾸고 마지막에 위치하는 선물 받을 갯수 리스트중 최댓값을 반환하면 문제는 해결된다.

 

최종 코드

import numpy as np
def solution(friends, gifts):
    answer = 0
    gift_mat = [[0 for _ in range(len(friends))] for _ in range(len(friends))]
    gift_rating=[[0 for _ in range(4)] for _ in range(len(friends))]
    #선물 기록 매트릭스 초기화
    # for i in range(0,len(friends)):
        # gift_rating[i][0]=friends[i]

    #선물 기록 매트릭스 만들기
    for j in range(0,len(gifts)):
        gift_from=gifts[j].split(" ")[0]
        from_index=friends.index(gift_from)
        gift_to=gifts[j].split(" ")[1]
        to_index=friends.index(gift_to)
        gift_mat[from_index][to_index]=gift_mat[from_index][to_index]+1
    
    #선물 지수 계산
    for index in range(0,len(friends)):
        gift_rating[index][0]=sum(gift_mat[index])
        gift_rating[index][1] = sum(np.array(gift_mat).T[index])
        gift_rating[index][2]=gift_rating[index][0]-gift_rating[index][1]
    
    #선물 받는 횟수 계산
    for i in range(0,len(gift_mat)):
        for j in range(0,len(gift_mat)):
            if i==j:
                continue
            elif gift_mat[i][j]>gift_mat[j][i]:
                gift_rating[i][3]=gift_rating[i][3]+1
            elif gift_mat[i][j]==gift_mat[j][i]:
                if gift_rating[i][2]>gift_rating[j][2]:
                    gift_rating[i][3]=gift_rating[i][3]+1
                    
    answer=int(max(np.array(gift_rating).T[3]))
    return answer

 

p.s

위 최종 코드에서는 선물 기록 리스트인 gift_rating의 각 행 첫번째 요소를 친구 리스트의 요소로 설정하는 반복문이 들어있는데 최종적으로는 코드에서 제외하였다. 그 이유로는 테스트 케이스에서는 별 문제 없이 동작을 하였지만 제출후 점검에서는 해당 라인으로 인해 절반 넘게 실패를 하여서 혹시나 하는 마음으로 제외하고 제출을 하니 잘 동작하였다. 왜 그런지 이유는 아직 모르겠다...