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

코드 힌트

1. 친구들의 인덱스 저장

• HashMap<String, Integer>을 사용하여 친구 이름을 인덱스로 저장합니다.
• 이렇게 하면 친구의 이름을 인덱스로 빠르게 변환할 수 있습니다.

2. 선물 지수 배열 만들기

• 각 친구가 받은 선물의 지수를 저장할 배열 giftIndex를 만듭니다.
• 선물을 줄 때마다 주는 사람의 지수를 증가시키고 받는 사람의 지수를 감소시킵니다.

3. 선물 주고받은 횟수 기록

• 친구 간의 선물 주고받은 횟수를 기록할 2차원 배열 recode를 만듭니다.
• 각 친구가 서로 몇 번씩 선물을 주고받았는지 기록합니다.

4. 선물 지수 및 주고받은 횟수 업데이트

• 주고받은 선물 정보를 바탕으로 각 친구의 선물 지수와 주고받은 횟수를 업데이트합니다.

5. 다음 달 받을 선물 수 계산

• 각 친구가 다음 달에 받을 선물 수를 계산합니다.
• 친구 간의 선물 주고받은 횟수를 비교하여 받을 선물 수를 추정합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        // key : 이름, value : friends 배열의 index
        // giftIndex, recode의 index(식별자 역할)를 파악하기 위한 HashMap
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < friends.length; i++) {
            map.put(friends[i], i);
        }
        
        // 선물 지수 저장 배열
        // map에 저장된 index를 활용하여 선물 지수 저장
        int[] giftIndex = new int[friends.length];
        
        // 친구마다 선물 준 횟수를 저장하는 2차원 배열
        // (ex : 0번째 친구는 1,2,3,4에게, 1번째 친구는 0,2,3,4에게 준 횟수 카운트)
        int[][] recode = new int[friends.length][friends.length];
        
        // 선물 지수 및 선물 주고받은 횟수 저장
        for (int i = 0; i < gifts.length; i++) {
            // 0번째는 선물 한 친구 이름, 1번째는 선물 받은 친구 이름
            String[] gift = gifts[i].split(" ");
            
            // 선물 지수 증가 (선물 한 친구)
            giftIndex[map.get(gift[0])]++;
            // 선물 지수 감소 (선물 받은 친구)
            giftIndex[map.get(gift[1])]--;
            
            // 선물 주고받은 횟수 저장
            recode[map.get(gift[0])][map.get(gift[1])]++;
        }
        
        // 다음 달에 가장 많은 선물을 받는 친구의 최대 선물 수 저장 변수
        int result = 0;
        
        // 각 친구가 다음 달에 받을 선물 수 계산
        for (int i = 0; i < friends.length; i++) {
            // i번째 친구가 받을 선물 수 초기화
            int cnt = 0;
            // 모든 친구들과 비교하여 선물 수 계산
            for (int j = 0; j < friends.length; j++) {
                // 자기 자신과 비교하는 경우 건너뜀
                if (i == j) continue;
                
                // i가 j에게 준 선물이 j가 i에게 준 선물보다 많을 때 cnt 증가
                if (recode[i][j] > recode[j][i]) cnt++;
                // i와 j가 서로 똑같이 주거나 주지는 않았지만 i의 선물 지수가 더 높을 때 cnt 증가
                else if (recode[i][j] == recode[j][i] && giftIndex[i] > giftIndex[j]) cnt++;
            }
            
            // 최대 선물 수 갱신
            result = Math.max(result, cnt);
        }
        
        return result;
    }
}

 

주석 제거한 답

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < friends.length; i++) {
            map.put(friends[i], i);
        }
        
        int[] giftIndex = new int[friends.length];
        int[][] recode = new int[friends.length][friends.length];
        
        for (int i = 0; i < gifts.length; i++) {
            String[] gift = gifts[i].split(" ");
            
            giftIndex[map.get(gift[0])]++;
            giftIndex[map.get(gift[1])]--;
            
            recode[map.get(gift[0])][map.get(gift[1])]++;
        }
        
        int result = 0;
        for (int i = 0; i < friends.length; i++) {
            int cnt = 0;
            for (int j = 0; j < friends.length; j++) {
                if (i == j) continue;
                
                if (recode[i][j] > recode[j][i]) cnt++;
                else if (recode[i][j] == recode[j][i] && giftIndex[i] > giftIndex[j]) cnt++;
            }
            result = Math.max(result, cnt);
        }
        return result;
    }
}