[Programmers] 선물 주고받기 계산 (Java)

- 알고리즘 분류 : 구현
- 사용 언어 : JAVA

(효율성 테스트가 없어 생각나는대로 작성)

1. 초기 세팅

• giftMap:
  → 친구들끼리 누가 누구에게 몇 번 선물했는지 저장하는 2차원 Map.
  (예: giftMap["A"]["B"] = 2 → A가 B에게 선물 2번 줌)
• summaryMap:
  → 각 친구의 총 준 선물 수(GIVE), 받은 선물 수(RECEIVE), 그리고
  선물지수(SCORE = GIVE - RECEIVE) 를 저장하는 Map.

요약:
→ 선물 내역과 선물지수를 따로 정리할 준비를 함.

---

2. 선물 기록 파싱

• gifts 배열을 순회하면서 "sender receiver" 형태를 split 해서
  → sender가 receiver에게 선물한 횟수를 1 추가함.
• 그리고 summaryMap에서:
  • sender의 GIVE +1
  • receiver의 RECEIVE +1
  • 둘 다 SCORE(GIVE - RECEIVE) 재계산

요약:
→ 선물을 주고받을 때마다 각각의 보낸 개수, 받은 개수, 선물지수를 최신화.

---

3. 누가 추가 선물을 받을지 계산

• 모든 친구를 2명씩 짝지어서 비교 (i, j 루프)
• 서로 주고받은 선물 수를 비교해서:
  • 더 많이 준 사람이 추가 선물 1개를 얻음.
• 만약 주고받은 수가 같으면:
  • 선물지수(SCORE)가 더 높은 사람이 추가 선물 1개 얻음.
• 이 결과를 totalMap에 저장.
  (totalMap["A"] = 3 → A는 최종적으로 3개 추가 선물 받음)

---

4. 최종 답 구하기

• totalMap을 순회하면서
  → 가장 많이 선물을 추가로 받은 친구의 개수(maxGiftCount) 를 구해서 리턴.

 

import java.util.*;
class Solution {
    public int solution(String[] friends, String[] gifts) {
        final String GIVE = "GIVE";
        final String RECEIVE = "RECEIVE";
        final String SCORE = "SCORE";
        
        Map<String, Map<String, Integer>> giftMap = new HashMap<>();
        Map<String, Map<String, Integer>> summaryMap = new HashMap<>();
        
        // 표 작성
        for (String cur : friends) {
            // 1. 선물 표
            Map<String, Integer> curMap = new HashMap<>();
            for (String name : friends) {
                curMap.put(name, 0);
            }
            giftMap.put(cur, curMap);
            
            // 2. 선물지수 표
            Map<String, Integer> curSummaryMap = new HashMap<>();
            curSummaryMap.put(GIVE, 0);
            curSummaryMap.put(RECEIVE, 0);
            curSummaryMap.put(SCORE, 0);
            summaryMap.put(cur, curSummaryMap);
        }
        
        for (String gift : gifts) {
            String[] giftArr = gift.split(" ");
            String sender = giftArr[0];
            String receiver = giftArr[1];
            
            // 발신쪽
            Integer giftCount = giftMap.get(sender).get(receiver);
            giftMap.get(sender).put(receiver, giftCount+1);
            
            Integer giveCount = summaryMap.get(sender).get(GIVE);
            Integer receiveCount = summaryMap.get(sender).get(RECEIVE);
            giveCount++;
            summaryMap.get(sender).put(GIVE, giveCount);
            summaryMap.get(sender).put(SCORE, (giveCount - receiveCount));
            
            receiveCount = summaryMap.get(receiver).get(RECEIVE);
            giveCount = summaryMap.get(receiver).get(GIVE);
            receiveCount++;
            summaryMap.get(receiver).put(RECEIVE, receiveCount);
            summaryMap.get(receiver).put(SCORE, (giveCount - receiveCount));
        }
        
        // 계산시작
        Map<String, Integer> totalMap = new HashMap<>();
        
        for (int i=0; i<friends.length; i++) {
            String cur = friends[i];
            for (int j=i+1; j<friends.length; j++) {
                String name = friends[j];
                Integer curGiveCount = giftMap.get(cur).get(name);
                Integer nameGiveCount = giftMap.get(name).get(cur);
                
                if (curGiveCount > nameGiveCount) {
                    if (totalMap.get(cur) == null) {
                        totalMap.put(cur, 1);
                    } else {
                        totalMap.put(cur, totalMap.get(cur) + 1);
                    }
                } else if (curGiveCount < nameGiveCount) {
                    if (totalMap.get(name) == null) {
                        totalMap.put(name, 1);
                    } else {
                        totalMap.put(name, totalMap.get(name) + 1);
                    }
                } else { // 선물지수로 비교
                    Integer curScore = summaryMap.get(cur).get(SCORE);
                    Integer nameScore = summaryMap.get(name).get(SCORE);
                    
                    if (curScore > nameScore) {
                        if (totalMap.get(cur) == null) {
                            totalMap.put(cur, 1);
                        } else {
                            totalMap.put(cur, totalMap.get(cur)+1);
                        }
                    } else if (curScore < nameScore) {
                        if (totalMap.get(name) == null) {
                            totalMap.put(name, 1);
                        } else {
                            totalMap.put(name, totalMap.get(name)+1);
                        }
                    }
                }
            }
        }
        
        int maxGiftCount = 0;
        for (String name : friends) {
            if (totalMap.get(name) != null) {
                maxGiftCount = Math.max(maxGiftCount, totalMap.get(name));
            }
            
        }
        
        return maxGiftCount;
    }
}

 

소스 설명은 주석을 참고해주세요.