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

문제

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

프로그래머스

 

---

 

문제 개요

주어진 친구 목록과 선물 기록을 바탕으로, 다음 달에 누가 가장 많은 선물을 받을지 계산하는 문제입니다. 두 사람이 선물을 주고받은 횟수와, 주고받은 기록이 없을 경우 각자의 선물 지수를 비교하여 규칙에 따라 선물을 받는 사람을 결정합니다. 가장 많은 선물을 받을 친구가 받을 선물의 개수를 반환해야 합니다.

 

 

접근 방법

1. 데이터 초기화 및 매핑
   • give와 receive라는 두 개의 맵을 사용해 각 친구가 준 선물과 받은 선물의 기록을 저장합니다.
   • 선물 기록(gifts)을 순회하며 각 친구의 선물 데이터를 업데이트합니다.
2. 선물 예측
   • 모든 친구 쌍을 순회하며 두 사람 간의 선물 횟수를 비교합니다.
   • 두 사람 간의 선물 기록이 없거나 동일한 경우, 선물 지수를 계산하여 비교합니다.
     • 선물 지수 = 자신이 준 선물의 수 - 자신이 받은 선물의 수
   • 비교 결과에 따라 선물을 받는 친구를 결정하고 카운트를 증가시킵니다.

 

 

코드

import java.util.*;

class Solution {
    static Map<String, List<String>> give = new HashMap<>();
    static Map<String, List<String>> receive = new HashMap<>();
    
    public int solution(String[] friends, String[] gifts) {
        int answer = 0;
        initMap(friends, gifts);
        int[] res = predict(friends);
        return res[res.length-1];
    }
    
    public void initMap(String[] friends, String[] gifts) {
        for(String s : friends) {
            give.put(s, new LinkedList<>());
            receive.put(s, new LinkedList<>());
        }
        
        for(String s : gifts) {
            String[] arr = s.split(" ");
            give.get(arr[0]).add(arr[1]);
            receive.get(arr[1]).add(arr[0]);
        }
    }
    
    public int[] predict(String[] friends) {
        int[] res = new int[friends.length];
        
        for(int i=0; i<friends.length-1; i++) {
            for(int j=i+1; j<friends.length; j++) {
                String a = friends[i];
                String b = friends[j];
                
                int aNum = getGiveCnt(a, b);
                int bNum = getGiveCnt(b, a);
                
                if(aNum > bNum) {
                    res[i]++;
                } else if (bNum > aNum) {
                    res[j]++;
                } else {
                    int aGiftIdx = give.get(a).size() - receive.get(a).size();
                    int bGiftIdx = give.get(b).size() - receive.get(b).size();
                    
                    if(aGiftIdx > bGiftIdx) {
                        res[i]++;
                    } else if (bGiftIdx > aGiftIdx) {
                        res[j]++;
                    }
                }
            }
        }
        
        Arrays.sort(res);
        return res.clone();
    }
    
    public int getGiveCnt(String giveMan, String receiveMan) {
        int cnt = 0;
        for(int i=0; i<give.get(giveMan).size(); i++) {
            if(give.get(giveMan).get(i).equals(receiveMan)) cnt++;
        }
        return cnt;
    }
}