[Programmers / Level 1] 258712. 가장 많이 받은 선물 / 2024 KAKAO WINTER INTERNSHIP (Java)

💡 Info

• 난이도: Lv1
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/258712
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/1/가장 많이 받은 선물

입출력 조건

입출력 예시

문제 이해

• 친구들 간의 선물 내역을 분석하여 각 친구가 다른 친구들보다 더 많이 선물을 준 횟수를 비교하고, 그 중 최대 값을 반환하는 문제
  
  
  
  

알고리즘

풀이 시간 : 68분

• 해시맵 사용
• 선물을 준 사람과 받은 사람 기록
  • 선물 준 횟수 +1, 받은 횟수 -1로 -> giftDegree
  • giftGraph 배열에 선물 관계 기록
• 선물 관계 비교
  • 특정 친구가 다른 친구보다 더 많이 주거나 같다면
    • 선물 지수가 더 크다면 카운트 증가
• 가장 높은 값으로 갱신
• 가장 많이 선물을 주고받은 경우의 수 반환

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int n = friends.length;
        
        Map<String, Integer> friendIndex = new HashMap<>();
        for (int i = 0; i < n; i++) {
            friendIndex.put(friends[i], i);
        }

        int[] giftDegree = new int[n];
        int[][] giftGraph = new int[n][n];

        for (String gift : gifts) {
            String[] parts = gift.split(" ");
            int giver = friendIndex.get(parts[0]);
            int receiver = friendIndex.get(parts[1]);

            giftDegree[giver]++;
            giftDegree[receiver]--;
            giftGraph[giver][receiver]++;
        }

        int maxCount = 0;

        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && (giftGraph[i][j] > giftGraph[j][i] || 
                    (giftGraph[i][j] == giftGraph[j][i] && giftDegree[i] > giftDegree[j]))) {
                    count++;
                }
            }
            maxCount = Math.max(maxCount, count);
        }

        return maxCount;
    }
}

결과