가장 많이 받은 선물 -2-

어제에 이어 가장 많이 받은 선물 알고리즘 문제를 풀었다.

어제 [선물 준 사람 A : [A에게 선물 받은 사람 : 받은 횟수]] 형태의 이중 딕셔너리 giftRecord를 만들어 누가 누구에게 몇 번 선물을 주었는지 담아놓는 것까지 했었다.

문제 입력 예시와 테스트 출력

이제 여기서 A와 B 두 사람의 선물 주고받은 횟수를 비교하여 다음달은 누가 선물을 받을지 정하는 로직을 짠 뒤, 가장 많이 받게 될 사람을 뽑아내면 된다.

---

값 출력 먼저 해보기

이중 딕셔너리를 다루는게 좀 헷갈려서, 일단 A가 B에게 준 선물 횟수와 반대로 B가 A에게 준 선물 횟수를 각각 뽑아낼 수 있는지부터 해보았다.

for(giver, receivers) in giftRecord를 통해 선물 기록이 담긴 giftRecord의 키를 giver로, 밸류를 receivers로 하여 접근하였다. giver는 선물을 한 사람, receivers는 giver에게 선물을 받은 사람들과 선물 받은 횟수가 저장된 딕셔너리이다.

이후 다시 for문으로 receivers의 키와 밸류를 각각 receiver과 count로 하여 접근하였다.

이렇게 하면 giver에 선물한 사람들의 이름이 반복해서 하나씩 들어올 것이고, receiver에 giver에게 선물을 받은 사람들의 이름이, count에 선물 받은 횟수가 들어올 것이다.

그리고 giftRecord에서 현재 receiver의 이름을 키로 접근하면, 이 선물을 받은 B가 A에게 선물을 몇 번 주었는지도 알 수 있다. 그걸 확인하기 위해 giftRecord[receiver][giver] 형태로 하여, 현재 선물을 한 giver가 선물 받은 receiver에게, 반대로 선물을 몇 번 받았는지 확인해보았다.

---

조금 수정하기

이렇게 해보니 출력은 잘 되는 거 같은데, 코드를 자세히 보니 조금 이상했다. 이중 for문으로 giftRecord에 접근해 값을 뽑아냈는데, 이 이중 for문을 감싸는 for문이 하나 더 있다.

giftRecord를 만들 때 입력 값인 gifts에서 선물 준 사람과 선물 받은 사람을 구분해 냈던 것을 그대로 가져다 쓴 건데, 여기선 giftRecord에서 각각 giver와 receiver를 가져오니 필요가 없다. 그래서 다음과 같이 조금 수정하였다.

가장 상위의 for문을 지운 것이다. 이렇게 해도 누가 A가 B에게, B가 A에게 몇 번 선물했는지 출력할 수 있다.

---

선물 지수 구하기

이제 이 상태에서 A와 B의 선물 기록을 비교해 다음달에 누가 선물을 받을지 정하면 되는데, 선물 기록이 같거나 없으면 선물 지수를 비교해야 한다.

선물 지수를 구하는 코드를 먼저 작성하기로 했다.

선물 지수 계산을 위해선 한 사람이 준 모든 선물의 갯수와 받은 모든 선물의 갯수를 저장해야 한다.

선물을 준 갯수를 [선물 준 사람 이름 : 선물 준 갯수] 형태로 저장할 givePresentCount 딕셔너리를 선언하였고, 반대로 받은 갯수를 저장하기 위해 [선물 받은 사람 이름 : 선물 받은 갯수] 형태의 receivePresentCount 딕셔너리를 선언하였다. 그리고 선물지수를 저장할 딕셔너리 presentIndex도 선언하였다.

이후 위에서 A가 B에게 선물 준 횟수를 출력할 때 처럼 이중 for문으로 giftRecord의 값에 접근해 givePresentCount의 키를 giver로 하여 givePresentCount[giver]의 값인 'giver(선물 준 사람)의 선물 준 횟수'를 더하도록 작성하였다.

그리고 같은 사람이 선물을 받은 횟수를 저장하기 위해 receivePresentCount[giver]에, 위에서 확인했던 B(선물 받은 사람 receiver)가 A(선물 준 사람 giver)에게 준 선물의 값인 giftRecord[receiver][giver]를 대입하였다.

그렇게 해서 새로운 반복문에 givePresentCount랑 receivePresentCount, 그리고 이 둘을 빼서 만든 선물지수 presentIndex를 출력해 확인해보았다.

잘못된 결과화면

음.. 무언가 잘못 되었다.

muzi는 2번 선물하고 5번 받아서 선물지수가 5이고, ryan은 3번 주고 1번 받아서 2여야 하는데, frodo랑 neo만 맞고 muzi랑 ryan은 틀렸다.

아마 frodo랑 neo도 우연히 맞은거지 아마 로직 자체가 틀려먹었을 것이다..

다시 잘 살펴보면 선물 준 횟수는 다 맞다. 받은 횟수가 틀렸고 그래서 선물지수도 틀린것이다.

givePresentCount에는 선물 준 횟수를 더하니까 += count 하는게 맞고, 그래서 선물 준 횟수는 맞을 수밖에 없다. 문제는 receivePresentCount에 값을 넣는게 잘못 된 것이다.

---

로직 수정하기

위에서 처음에 작성했던 출력 코드를 for문 안에 넣어 count와 giftRecord[receiver][giver]의 값, 그리고 givePresentCount와 receivePresentCount의 값이 어떻게 변하는지 확인해보았다.

처음엔 한 반복문에서 giver와 receiver가 있을 때, giver가 준 선물 갯수인 count를 givePresentCount[giver]에 누적 시키면 giver가 준 선물의 총합이 구해지고, receiver가 준 선물 갯수를 receivePresentCount[giver]에 저장하면 giver가 받은 선물의 총합이 구해질 것이라고 생각했던 것이다.

그런데 giftRecord[receiver][giver]의 값을 대입하면 B가 A에게 준 선물 갯수, 즉 해당 반복문에서의 receiver가 해당 giver에게 준 선물의 갯수만 더해지게 되어 누락이 발생한다. 

이렇게 할 게 아니고, giver든 receiver든 한 사람이 받은 모든 선물 갯수를 더해야하므로 giver가 준 선물 갯수인 count를 receivePresentCoutn[receiver]에 누적시키면, receiver가 받은 선물 갯수가 누적 될 것이다.

코드를 위와같이 수정하였다. receivePresentCount의 키를 giver에서 receiver로 변경하고, 대입하는 값을 giftRecord[receiver][giver]에서 count로 변경하였다.

준 선물과 받은 선물이 모두 잘 저장되니 선물지수도 잘 계산되어 저장되었다.

---

다음달 선물 정하기

이제 가장 중요한 부분이 남았다. 다음달 선물 갯수를 정하는 것이다.

위에서 확인 해봤듯이, A가 B에게 준 선물 갯수는 giftRecord에서 키를 A로 하여 접근해 나온 하위 딕셔너리에서 다시 키를 B로 하여 접근하면 반환된다. 이걸 코드로 쓰면 giftRecord[A][B]가 될 것이다. 반대로 B가 A에게 준 건 giftRecord[B][A] 형태이다.

입력 값인 friends 배열에 이름이 하나씩 저장되어 있으므로 이 배열을 이중반복문으로 비교할 A와 B의 이름을 하나씩 뽑아서 두 값을 비교하면 누가 선물을 받을 지 정할 수 있다.

위와 같이 선물 갯수를 정하는 부분을 작성하였다. 다음달에 누가 선물을 몇 개 받게될지 저장하는 presentCount를 딕셔너리로 선언하였고 이중반복문으로 두 사람의 선물 주고받은 갯수를 비교한 것이다.

첫 if문은 A가 B보다 선물을 많이 줬을 경우, else if문은 둘이 같을 경우, else문은 B가 A보다 많이 줬을 경우이다.

print() 때문에 코드가 좀 길어 보이지만, 필요한 부분만 남기면 다음과 같다.

물론 실행은 결과 확인을 위해 print가 있는 코드를 실행할 것이다.

결과가 잘 나와서 문제에 나온 다른 예시들도 출력해보았고, 이번에는 print() 출력문을 없애고 반환만 받아 마무리 하도록 하였다.

---

전체 코드

import Foundation

func solution(_ friends:[String], _ gifts:[String]) -> Int {
    var presentCount: [String : Int] = [:] // 다음달 예상 선물 개수
    var presentIndex: [String : Int] = [:] // 선물 지수
    
    // 이름을 키로 하는 이중 딕셔너리 생성
    var giftRecord: [String : [String:Int]] = [:]
    for friend in friends {
        giftRecord["\(friend)"] = [:]
    }

    for record in gifts {
        let splitRecord = record.components(separatedBy: " ")
        let giver = splitRecord[0] // 선물 준 사람
        let reciver = splitRecord[1] // 선물 받은 사람
        
        giftRecord[giver]?[reciver, default: 0] += 1 // [받은 사람: 받은 횟수] 딕셔너리에 키를 reciver로 하는 딕셔너리의 밸류(receiver의 받은 횟수) +1 하기
    }
    
    //선물 지수 먼저 계산 해놓기
    var giverPresentCount: [String : Int] = [:] // giver가 receiver들에게 선물 준 횟수 카운트
    var receiverPresentCount: [String : Int] = [:] // giver가 receiver들에게 받은 선물 횟수 카운트
    for (giver, receivers) in giftRecord { // giver - 선물 준 사람, receivers - [giver에게 선물 받은 사람들 : 받은 횟수]
        for (receiver, count) in receivers { // receiver : 선물 받은 사람, count: receiver가 받은 선물 횟수

            giverPresentCount["\(giver)", default: 0] += count // giver가 receiver들에게 준 선물 갯수 누적 => [giver : count]
            receiverPresentCount["\(receiver)", default: 0] += count //receiver가 giver에게 받은 선물 갯수 누적 => [receiver : count]
        }
    }
    for friend in friends {
        presentIndex[friend] = (giverPresentCount[friend] ?? 0) - (receiverPresentCount[friend] ?? 0)
    }
    
    // 다음달 선물 갯수
    for i in 0..<friends.count {
        for j in (i+1)..<friends.count {
            let giverPresent = giftRecord[friends[i]]?[friends[j]] ?? 0 // A가 B에게 준 선물 갯수
            let receiverPresent = giftRecord[friends[j]]?[friends[i]] ?? 0 // B가 A에게 준 선물 갯수
            
            if giverPresent > receiverPresent { // A가 B에게 준 선물 갯수가 B가 A에게 준 선물 갯수보다 많다면
                presentCount["\(friends[i])", default: 0] += 1 // A의 다음달 선물 갯수 +1
            }
            else if giverPresent == receiverPresent || (giverPresent == 0 && receiverPresent == 0)  { // A와 B가 주고받은 선물의 갯수가 같거나 주고받은 기록이 없을때 선물 지수 비교
                if presentIndex["\(friends[i])", default: 0] > presentIndex["\(friends[j])", default: 0] { // A의 선물지수가 B보다 크다면
                    presentCount["\(friends[i])", default: 0] += 1 // A의 다음달 선물 갯수 +1
                } else if presentIndex["\(friends[i])", default: 0] < presentIndex["\(friends[j])", default: 0] { // B의 선물지수가 A보다 크다면
                    presentCount["\(friends[j])", default: 0] += 1 // B의 다음달 선물 갯수 +1
                }
            }
            else if giverPresent < receiverPresent { // B가 A에게 준 선물 갯수가 A가 B에게 준 선물 갯수보다 많은 경우
                presentCount["\(friends[j])", default: 0] += 1 // B의 다음달 선물 갯수 +1
            }
        }
    }
    
    //결과 반환
    if let maxCount = presentCount.max(by: { $0.value < $1.value }) {
        return maxCount.value
    } else {
        return 0
    }
}