Lv 1. 가장 많이 받은 선물

YeongHyeon Jo·2024년 3월 5일

algorithm swift

Algorithm

목록 보기

7/10

문제의 해결 방법

A 친구의 선물을 준 상대에 대해 정리한다.
A 외 다른 친구들도 동일하게 선물을 준 상대에 대해 정리한다.
각 친구들의 '선물을 준 수' - '선물을 받은 수' 값을 정리한다.
아래의 조건을 만족하는 경우 다음달에 선물을 줄 수 있게한다.
1) 선물을 준사람이 받은 사람보다 더 많은 선물을 준 경우 받은 사람이 준 사람에게 선물을 준다.
2) 선물을 주고받지 않았거나, 선물을 주고받은 수가 동일한 경우 3번에서 계산한 값이 더 큰 사람이 작은 사람에게 선물을 받는다.

1. 친구들이 준 선물 정리

1) 우선 친구들을 각각 구분을 해줘야한다.

나는 각 친구들에 대한 순서를 나의 임의대로 지정해주기 위해서 Dictionary로 선언하고 추후 이를 통해 선물을 주고 받은 상대를 기억하기 위해서이다.
(*앞으로 실행은 제일 첫번째 예를 가지고 진행을 할 것이다.)

var friendsInfo: [String: Int] = [:]
for (index, friend) in friends.enumerated() {
	friendsInfo[friend] = index
}
// ["neo": 3, "frodo": 2, "ryan": 1, "muzi": 0]

2) 주고 받은 사람을 표시하는 표를 만든다.

이제 gifts를 보면 준 사람과 받은 사람을 표시하여 이를 통해 누가 누구에게 주었는지 확인하기 위해 틀을 만들어보자.
아래의 코드를 보게되면 Array(repeating: 반복할 값, count: 반복할 횟수) 이러한 형태를 볼 수 있는데, 이는 친구들의 수만큼의 표를 만들기 위해서 생성하였다. 아직 선물을 받기 전의 상태임으로 0으로 모두 초기화를 하였다.

var giveGifts: [[Int]] = [[Int]](repeating: [Int](repeating: 0, count: friends.count), count: friends.count)
// [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
// 실질적으로 원하는 값은 아래와 같다.
//		 muzi	ryan	frodo	neo
// muzi   0		 0		  0      0
// ryan   0		 0		  0      0
// frodo  0		 0		  0      0
// neo    0		 0		  0      0

이제 이렇게 만들었으면 각 표에 값을 채워야 한다.

우선 선물의 형태를 보자 "muzi frodo" 와 같이 String 형태로 정의되어있는데, 이는 muzi가 frodo에게 선물을 주었다라는 뜻이다.

for gift in gifts {
	let giverReceiver = gift.split(separator: " ").map { String($0) }
    if let giver = giverReceiver.first, let receiver = giverReceiver.last {
		if let giverIndex = friendsInfo[giver], let receiverIndex = friendsInfo[receiver] {
			// 1. 주고 받은 사람을 표시한다.
			giveGifts[giverIndex][receiverIndex] += 1 // giver의 배열에 receiver의 값을 1 올려준다.
		}
	}
}

split을 통해 "muzi frodo"를 " " 기준으로 구분하여 각각 이를 분류해주었다. 여기에서 첫번째 값과 두번째 값을 구분하기 위해서 giverReceiver.first, giverReceiver.last를 사용하였다. 이때 .first와 .last는 만약에 데이터가 없을수도 있기 때문에 Optional형태로 출력이 된다. 위의 데이터를 실행하는 경우 아래와 같이 출력이 된다.

print(giverReceiver.first) // Optional("muzi")
print(giverReceiver.last) // Optional("frodo")

그렇기 때문에 if let을 통해 Optional Binding을 하여 안전하게 값을 추출해낸다.
또한 위에서 친구들의 정보들 또한 friendsInfo에 Dictionary 형태로 저장하였기 때문에 이를 추출할 때 키가 Dictionary에 없을 경우를 대비하여 옵셔널로 반환이된다. 그리하여 if let을 중복으로 사용하여 데이터 값을 추출하였다.

split vs components

처음에 문자열을 분할하기 위하여 split을 사용하였는데, 검색을 하다보니 components가 있다는 것을 확인하게 되었다.

split
- Swift 표준 라이브러리에 속해있어서 import할 필요가 없다.
- [SubString]를 반환한다.
(*SubString은 간단하게 String을 분리한 형태로 메모리 상에서 SubString은 String의 주소를 참조해서 값을 가지고 있어 메모리 성능 측면에서 최적화가 되어있다.)
components
- Foundation 프레임워크에 속해있어서 import해야한다.
- [String]를 반환한다.

3. 각 친구들마다 선물 지수 계산한다.

선물 지수란 '선물을 준 수' - '선물을 받은 수' 이를 계산한 값이다.
우선 위와 같이 계산하기 전 초기값을 설정해준다.

var giftCount: [Int] = [Int](repeating: 0, count: friends.count)
// [0, 0, 0, 0]

그리고 위에서 선물을 줄 때마다 실행이 되는 반복문에 넣어서 실행을 할텐데, 여기서 생각해야 하는 점은

선물을 주는 경우 -> 선물 지수에서 + 1
선물을 받는 경우 -> 선물 지수에서 - 1

이와 같은 조건을 만족한다.
그렇다면 위의 반복문 코드에 적용하게 되면 아래와 같이 giverIndex가 적용된 선물 지수는 +1, receiverIndex가 적용된 선물 지수는 -1이 된다.

for gift in gifts {
	let giverReceiver = gift.split(separator: " ").map { String($0) }
    if let giver = giverReceiver.first, let receiver = giverReceiver.last {
		if let giverIndex = friendsInfo[giver], let receiverIndex = friendsInfo[receiver] {
			// 1. 주고 받은 사람을 표시한다.
			giveGifts[giverIndex][receiverIndex] += 1
            // 2. 선물 지수를 계산해준다.
			giftCount[giverIndex] += 1
			giftCount[receiverIndex] -= 1
		}
	}
}

4. 다음달에 받는 선물의 수를 계산한다.

이제 위의 조건에 맞춰서 다음달에 추가적으로 받는 선물의 수를 계산해야한다.

1) 선물을 준사람이 받은 사람보다 더 많은 선물을 준 경우 받은 사람이 준 사람에게 선물을 준다.
2) 선물을 주고받지 않았거나, 선물을 주고받은 수가 동일한 경우 3번에서 계산한 값이 더 큰 사람이 작은 사람에게 선물을 받는다.

결과적으로 추가적으로 선물을 받는 사람의 값을 얻어야하니 받을 수 있는 조건을 기준으로 작성한다.

1) 첫번째 조건
선물을 주고받은 기록에서 준 사람이 받은 사람보다 커야한다.

giveGifts[giver][receiver] > giveGifts[receiver][giver]

2) 두번째 조건
선물을 주고 받지 않거나 주고받은 수가 동일한 경우 선물 지수가 높아야한다.
*선물을 주고 받지 않은 경우: 주고 받은 경우에만 +를 하였으므로 각각 0이므로 서로 값은 같다.

giveGifts[giver][receiver] == giveGifts[receiver][giver] && giftCount[giver] > giftCount[receiver]

이 두가지의 조건 중 하나를 만족해야한다! 코드를 작성해보자!

for giver in 0..<friends.count {
        // 다음달 받을 선물
        var giftToReceive: Int = 0
        
        for receiver in 0..<friends.count where giver != receiver {
            if giveGifts[giver][receiver] > giveGifts[receiver][giver]
                ||
                (giveGifts[giver][receiver] == giveGifts[receiver][giver] && giftCount[giver] > giftCount[receiver]) {
                giftToReceive += 1
            }
        }
    }

where 조건을 주가하여 giver와 receiver는 같을 수 없기 때문에 해당조건을 만족하는 경우에만 반복문을 실행하게 된다!

결과적으로 조건문을 만족하는 경우 받아야하는 선물의 수를 Count 해준다.

5. 가장 높은 값을 확인한다.

위에서 나온 결과를 비교하여 가장 높은 값을 얻어낸다.

result = max(result, giftToReceive)

max() 메서드를 이용하여 최종적으로 가장 높은 값을 얻어 낸다.

실행 결과

muzi
주고받은 현황: [0, 0, 2, 0]
선물지수: -3
다음달의 받을 선물: 1

ryan
주고받은 현황: [3, 0, 0, 0]
선물지수: 2
다음달의 받을 선물: 2

frodo
주고받은 현황: [1, 1, 0, 0]
선물지수: 0
다음달의 받을 선물: 1

neo
주고받은 현황: [1, 0, 0, 0]
선물지수: 1
다음달의 받을 선물: 2