[Kakao] 가장 많이 받은 선물

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

프로그래머스

 

 

 

위 문제를 풀면서

1. 이름들로 배열이 표현 될 경우, HashMap<String,Integer>을 통해 이름(String) - 인덱스(value) 형태로 저장 후,

value값인 인덱스를 array로 표현할 때 인덱스를 사용해본다.

 

이렇게  하면, 이름 -> 인덱스 -> 배열의 인덱스 로 사용이 가능해 표현이 더 간결해진다.

---

 

이 문제를 보고 기억해야 할 포인트는 두가지 이다.

1. 두 사람이 선물을 주고받은 기록이 있다면, 이번달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음달에 선물을 하나      받는다.

2. 두 사람이 선물을 주고받은 기록이 하나도 없거나 OR 주고받은 선물수가 같다면 선물 지수가 더 큰사람이 다음달에

    선물을 하나 받는다.

 

입출력 예시를 보면 알겠지만 friends의 이름으로 모든 그래프가 표현 되고 있고 문제에서도 friends의 배열을 통해서 이름들을 알려주고 있어서 이것을 인덱스로 사용하기에 좋아보였다.

 

그래서 Hashmap<String,Integer> 를 통해 muzi(key)-0(value) / ryan(key)-1(value) 같은 형태로 표현해 value를 어레이에서 인덱스로 사용할 생각이다.

 

간단히 말해, "어레이의 인덱스 =  friends의 이름 " 이 되는 것이다.

 

for(String gift : gifts){
            String[] name = gift.split(" ");
            giveDegree[map.get(name[0])]++;		// name[0] : 선물을 준 사람
            giveDegree[map.get(name[1])]--;		// name[1] : 선물을 받은 사람
            giftGraph[map.get(name[0])][map.get(name[1])]++;	
        }

 

또한 int[] giveDegree 즉, 선물지수를 위와 같이 표현해 선물을 주었을때는 +1로 선물지수를 올리고 선물을 받았을때는 -1로 선물지수를 내려, 해당 인덱스의 friends의 선물지수를 계산하였다.

 

그리고 아래 코드를 보면 2중 for-loop을 사용했는데, 이는 friends.length 즉 친구들의 수가 2 이상 50 이하로 작게 범위가 설정되어 사용했다. 코딩 테스트에서 2중 루프를 사용하기에 꺼려지지만 그럼에도 사용한 이유이다.

 

코드

import java.util.*;
class Solution {
    public int solution(String[] friends, String[] gifts) {
        int answer = 0;
        HashMap<String,Integer> map = new HashMap<>();        // friends의 각 이름을 0,1,2...와 매치시켜 어레이 인덱스로 쓰기위함.
        int[] giveDegree = new int[friends.length];                     // 선물 지수
        int[][] giftGraph = new int[friends.length][friends.length];    // 주고 받은 선물 그래프
        
        for(int i=0;i<friends.length;i++){
            map.put(friends[i],i);
        }
        
        for(String gift : gifts){
            String[] name = gift.split(" ");
            giveDegree[map.get(name[0])]++;		// name[0] : 선물을 준 사람
            giveDegree[map.get(name[1])]--;		// name[1] : 선물을 받은 사람
            giftGraph[map.get(name[0])][map.get(name[1])]++;	
        }
        
        for(int i=0;i<friends.length;i++){
            int num = 0;
            for(int j=0;j<friends.length;j++){
                if(i==j){
                    continue;
                }
                
                if(giftGraph[i][j] > giftGraph[j][i] || 			// 선물을 더 주었거나
                  (giftGraph[i][j] == giftGraph[j][i] && giveDegree[i] > giveDegree[j])){	// 주고받은 선물수가 같지만 선물지수가 더 클 경우
                    num++;
                }
            }
            
            answer = Math.max(answer,num);
        }
        
        
        return answer;
    }
}