[Programmers] 2024 KAKAO WINTER INTERNSHIP - 가장 많이 받는 선물 개수

 

 

문제

:친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측

 

■ 1. 문제  설명

 * 1. 두 사람이 선물을 주고받은 기록이 있다면, 
      이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.
 * 2. 두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 
      선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.
 * 3. 지수 = 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값

▶ String[] friends : 친구들 이름
▶ String[] gifts :친구들이 주고받은 선물 기록 (ex. "A(선물 준사람) B(선물 받은 사람)")

 

 

 

참고 :  주고받은 선물과 선물 지수를 표로 나타내면 아래와 같다.

 

★ Solution ! 주고받은 선물 기록을 기반으로, 가장 많은 선물을 받는 친구가 받을 선물의 수를  return 하도록 한다.

 

---

 

■ 2. 문제  풀이

 

(1) 유저별로 각각의 값을 매핑한다.

1. giverGiftCount  = {A : 4} => A 는 총 4개의 선물을 친구들에게 줌
2. receiverGiftCount = {A : 1} => A 는 총 1개의 선물을 친구들에게 받음
3. friedsGiftCounts = {A B : 3} => A 는 B 에게 총 3개의 선물을 줌

Map<String, Integer> giverGiftCount = new HashMap<>(); 
Map<String, Integer> receiverGiftCount = new HashMap<>();
Map<String, Integer> friendsGiftCounts = new HashMap<>();

 

 

(2) 선물 기록 list 를 조회 하면서 유저별로 각각의 값을  map 에 담는다.

1. 선물을 준 개수 

2. 선물을 받은 개수 

3. 선물을 준 사람과 선물받은 사람, 선물 준 개수 카운팅

for (String gift : gifts) {
    String giver = gift.split(" ")[0];
    String taker = gift.split(" ")[1];

    //getOrDefault : 찾는 key 가 존재한다면 찾는 key의 value를 반환하고 없거나 null 이라면 default 값을 반환
    giverGiftCount.put(giver, giverGiftCount.getOrDefault(giver, 0) + 1);
    receiverGiftCount.put(taker, receiverGiftCount.getOrDefault(taker, 0) + 1);
    friendsGiftCounts.put(gift, friendsGiftCounts.getOrDefault(gift, 0) + 1);
}

 

 

(3) 중첩 반복문을 돌면서, 사용자가 받을 선물의 수를 구하고 사용자간 그 수를 비교하여 max 값을 구한다.

1. tmp : 사용자가 받을 선물의 개수 (첫번째 for 문 사용자)

2. max : tmp 와 비교했을 때 더 큰 값

int max = 0;

for (int i = 0; i < friends.length; i++) {
    // 가장 큰 값을 찾기위해 tmp 변수 사용
    int tmp = 0;
    String friendI = friends[i];

    for (int j = 0; j < friends.length; j++) {

 

 

(5) 선물을 주고받은 기록이 있다면, 더 많은 선물을 준 사람 의 선물개수를 추가한다.

1. i 가 선물을 더 많이 줬다면, i 의 tmp 값 증가

2. j 가 선물을 더 많이 줬다면, 다음 반복문 실행

Integer iToj = friendsGiftCounts.getOrDefault(friendI + " " + friendJ, 0); // i가 j에게 준 선물의 개수
Integer jToi = friendsGiftCounts.getOrDefault(friendJ + " " + friendI, 0); // j가 i에게 준 선물의 개수

// 주고 받은 선물의 개수 비교
if (iToj > jToi) tmp++;
if (iToj != jToi) continue;

 

 

(6) 선물을 주고받은 기록이 하나도 없거나 같다면 선물 지수 비교

1. i 의 선물지수가 더 많다면, i 의 tmp 값 증가

// i와 j의 선물지수 구하기 (준선물 - 받은선물)
Integer iGiftCount = giverGiftCount.getOrDefault(friendI, 0) - receiverGiftCount.getOrDefault(friendI, 0);
Integer jGiftCount = giverGiftCount.getOrDefault(friendJ, 0) - receiverGiftCount.getOrDefault(friendJ, 0);

// 선물 지수 비교
if (iGiftCount > jGiftCount) tmp++;

 

 

(7) 가장 많은 선물을 받는 친구가 받을 선물의 수를 구한다.

1. 반복문을 돌면서, 사용자가 받을 선물의 개수가 순차적으로 tmp 변수에 담기고,

max 값과 비교해서 큰 값은 max 변수에 담는다. 그러면 반복문이 다 돌았을때 가장 큰 값을 구하게 된다.

max = Math.max(tmp, max);

 

 

 

 

★  전체 코드

public class Kakao {
    public int solution(String[] friends, String[] gifts) {

        Map<String, Integer> giverGiftCount = new HashMap<>(); 
        Map<String, Integer> receiverGiftCount = new HashMap<>(); 
        Map<String, Integer> friendsGiftCounts = new HashMap<>();

        for (String gift : gifts) {
            String giver = gift.split(" ")[0];
            String taker = gift.split(" ")[1];

            //getOrDefault : 찾는 key의 value 반화/ but 없거나 null 이라면 Default 반환
            giverGiftCount.put(giver, giverGiftCount.getOrDefault(giver, 0) + 1);
            receiverGiftCount.put(taker, receiverGiftCount.getOrDefault(taker, 0) + 1);
            friendsGiftCounts.put(gift, friendsGiftCounts.getOrDefault(gift, 0) + 1);
        }

        // 선물을 가장 많이 받을 친구 선물의 수
        int max = 0;

        for (int i = 0; i < friends.length; i++) {
            // 가장 큰 값을 찾기위해 tmp 변수 사용
            int tmp = 0;
            String friendI = friends[i];

            for (int j = 0; j < friends.length; j++) {
                if (i == j) continue;
                String friendJ = friends[j];

                Integer iToj = friendsGiftCounts.getOrDefault(friendI + " " + friendJ, 0); // i가 j에게 준 선물의 개수
                Integer jToi = friendsGiftCounts.getOrDefault(friendJ + " " + friendI, 0); // j가 i에게 준 선물의 개수

                // 주고 받은 선물의 개수 비교
                if (iToj > jToi) tmp++;
                if (iToj != jToi) continue;

                // i와 j의 선물지수 구하기 (준선물 - 받은선물)
                Integer iGiftCount = giverGiftCount.getOrDefault(friendI, 0) - receiverGiftCount.getOrDefault(friendI, 0);
                Integer jGiftCount = giverGiftCount.getOrDefault(friendJ, 0) - receiverGiftCount.getOrDefault(friendJ, 0);

                // 선물 지수 비교
                if (iGiftCount > jGiftCount) tmp++;
            }

            max = Math.max(tmp, max);
        }

        return max;
    }
}

 

 

★  결과

String[] friends = {"muzi", "ryan", "frodo", "neo"};
String[] gifts = {"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"};