[Programmers] 가장 많이 받은 선물 - Java

문제

프로그래머스

 

풀이

구현문제이다.

처음에 friends에 인덱스에 맞는 친구에게 준 횟수를 2차원 배열로 저장해야한다는 생각을 했다.

records[i][j] => i가 j에게 준 선물 횟수라고 생각했다. 

 

근데 gifts 배열을 보면 "이름 이름"의 형태로 준사람 받은 사람을 주고 있다.

"그러면 이름에 해당하는 인덱스를 순회해서 찾아야할까?"라는 생각을 했다.

 

하지만 생각해보면 그럴 필요가 없이, 이름에 해당하는 인덱스를 저장할 수 있는 자료구조인 HashMap을 사용해서 저장하면 된다고 생각했다.

 

그리고 사람 대 사람으로 1대1로 준 횟수에 대한 정보도 필요하지만, 그 사람이 다른 사람에게 준 전체 횟수와 받은 전체 횟수에 대한 정보도 필요하다.(indexMap)

이것도 for문을 수행하면서 횟수를 계산하는 것보다는, HashMap을 이용해서 횟수를 모두 기록하면 된다고 생각했다.(givenMap, takenMap)

 

풀이는 다음과 같다.

1. 인덱스 저장, 준 횟수, 받은 횟수 HashMap을 초기화한다.

2. 이름에 대한 인덱스를 저장한다.

3. 준 사람과 받은 사람을 찾아서 모두 HashMap과 records라는 2차원 배열에 저장한다.

4. 두 사람의주고 받은 횟수를 비교를 해서 처리한다.

4-1. 주고 받은 횟수가 동일하다면 선물 지수를 구해서 다음달 받을 횟수 배열을 증가시킨다.

4-2. 주고 받은 횟수가 다르다면, 횟수를 비교해서 다음달 받을 횟수 배열을 증가시킨다.

5. 다음달 받을 횟수 배열의 최댓값을 구한다.

 

소스코드

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        //이름이면 인덱스 반환 Map
        HashMap<String, Integer> indexMap = new HashMap<>();
        
        //주고 받은 기록 Map
        HashMap<String, Integer> givenMap = new HashMap<>(); 
        HashMap<String, Integer> takenMap = new HashMap<>();
            
        int friendCnt = friends.length;
        
        //주고 받은 횟수
        int[][] records = new int[friendCnt][friendCnt];
        
        //다음달 받은 선물의 수 저장 배열
        int[] cntArr = new int[friendCnt];
        
        //이름에 대해서 인덱스 저장
        for (int i = 0; i < friendCnt; i++) {
            indexMap.put(friends[i], i);
        }
        
        
        for (String gift : gifts) {
            String[] s = gift.split(" ");
            
            int from = indexMap.get(s[0]);
            int to = indexMap.get(s[1]);
            
            //from이 to에게 줬다는 선물 개수 증가
            records[from][to] += 1;
            
            //주고 받은 정보 기록 
            givenMap.put(s[0], givenMap.getOrDefault(s[0], 0) + 1);
            takenMap.put(s[1], takenMap.getOrDefault(s[1], 0) + 1);
        }
        
        for (int i = 0; i < friendCnt; i++) {
            for (int j = i + 1; j < friendCnt; j++) {
                //주고 받은 기록이 같다면(하나도 없어도 0으로 동일)
                if (records[i][j] == records[j][i]) {
                    //준사람 받은 사람
                    String givenPerson = friends[i];
                    String takenPerson = friends[j];
                    
                    //선물 지수(아예 기록이 없을 수 있어서 getOrDefault 사용)
                    int a = givenMap.getOrDefault(givenPerson, 0) - takenMap.getOrDefault(givenPerson, 0);
                    int b = givenMap.getOrDefault(takenPerson, 0) - takenMap.getOrDefault(takenPerson, 0);
                    //지수 비교해서 다음달 받을 선물 기록
                    if (a > b) {
                        cntArr[i] += 1;
                    } else if (a < b) {
                        cntArr[j] += 1;
                    }
                } else {
                    //주고 받은 기록으로 비교해서 다음 달 받을 선물 기록
                    if (records[i][j] > records[j][i]) {
                        cntArr[i] += 1;
                    } else if (records[i][j] < records[j][i]) {
                        cntArr[j] += 1;
                    }
                }
            }
        }
        
        //가장 많이 받을 선물의 수 계산
        int answer = 0;
        
        for (int cnt : cntArr) {
            answer = Math.max(cnt, answer);
        }
        
        return answer;
    }
}