[프로그래머스 python] 가장 많이 받은 선물

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

프로그래머스

 

 

처음 든 생각

- 일단 주어진 입출력의 풀이를 보면 두 개의 표가 등장한다. 이걸 어떻게 활용할 수 있을까?

- 첫번째 표는 유저의 수만큼의 정사각 행렬이다. -> 이차원 행렬로 나타내야겠다

- 두번째 표는 선물지수를 구하는 건데 준 선물의 총합과 받은 선물의 총합은 위의 이차원 행렬의 가로합과 세로합으로 구하면 된다.

- 비교의 순서는 주고받은 선물의 개수 확인 -> 똑같다면 선물 지수 확인

 

나의 답

def solution(friends, gifts):
	// 행렬에서 인덱스를 맞춰주기 위해 dict 선언
    friendsId = {}
    for i in range(len(friends)):
        friendsId[friends[i]] = i
        
    // 얘가 모든 계산의 본체
    tArray = [[0 for _ in range(len(friends))] for _ in range(len(friends))]
    
    // 이차원 행렬의 선물 개수 채워주기
    for gift in gifts:
        giver = gift.split(" ")[0]
        receiver = gift.split(" ")[1]
        giverId = friendsId[giver]
        receiverId = friendsId[receiver]
        tArray[giverId][receiverId] += 1
        
    // 선물 지수 계산 - friend의 인덱스와 sync 되게    
    giftIndexArray = []
    for i in range(len(friends)):
        tmp = 0
        for j in tArray:
            tmp += j[i]
        giftIndexArray.append(sum(tArray[i]) - tmp)
    
    nextMonthGiftArr = []
    
    // 순서대로 비교해가면서 다음달 선물 계산
    for i in range(len(friends)):
        nextMonthGift = 0
        for j in range(len(friends)):
            gived = tArray[i][j]
            received = tArray[j][i]
            if gived > received:
                nextMonthGift += 1
            elif gived == received:
                if giftIndexArray[i] > giftIndexArray[j]:
                    nextMonthGift += 1
        nextMonthGiftArr.append(nextMonthGift)
            
    
    return max(nextMonthGiftArr)

 

먼저 첫번째 목표는 예시 풀이처럼 이차원 행렬을 그리는 것이다.

이차원 행렬의 index를 맞춰주기 위해 딕셔너리를 하나 만들어서 조회하는 방식으로 하였다. index 메소드를 쓰면 O(n)이 추가되는 거라서 딕셔너리로 설정해주는 방식을 사용하였다. 

 

그 다음 0으로 채워진 이차 정사각 행렬을 만들어주고 선물 내역들을 반복문으로 돌면서 누가 누구에게 선물을 줬는지 하나씩 확인해서 반영해주면 된다.

 

선물지수를 계산하는 과정은 행의 합과 열의 합을 빼주면 되는 간단한 과정이다.

 

이제 다음달 받을 선물을 계산하면 된다.

한 사람을 기준으로 나머지 모든 사람들과 비교를 하면서 선물을 받을지 말지 결정을 하면 된다.

이차원 행렬에서 대각선에 있는 항들은 모두 자기 자신을 가리키는데 준 선물과 받은 선물이 동일하고 선물 지수도 같다면 선물을 주고받지 않는다는 것을 활용해 선물 개수 비교 -> 선물 지수 비교의 논리에서 같이 동작할 수 있게 된다.

 

그래서 본격적으로 계산을 해보자.

준 선물과 받은 선물을 비교하는 것은 행렬 원소의 대각선 반대 방향의 원소끼리 비교하면 된다. 그래서 준 선물이 더 많다면 하나를 더 받게 되고, 선물 개수가 같을 경우 선물 지수를 비교하면 된다. 선물 개수가 적다면 아무런 영향이 가지 않기 때문에 애초에 조건문 자체에서 확인해줄 필요가 없다.

 

선물 개수가 같은 경우 선물 개수가 같거나 그 이하면 받지 않기 때문에 큰 경우에만 선물을 하나 추가한다.

 

그렇게 순서대로 구한 결과를 하나씩 append해주면 인덱스가 friends의 순서와 sync가 맞기 때문에 각각의 다음달 선물을 구할 수 있다.

여기서 최대값을 리턴해주면 끝이다.

이 화면을 언제나 짜릿한 거 같다.

---

문제 푸는데 생각보다 오래 걸리기는 했지만 문제 자체를 완벽하게 이해한 후 순서대로 코드를 작성하면 무탈한 문제였다.

머리풀기로 풀어보기에는 아주 좋은 문제라고 생각된다.