가장 많이 받은 선물

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

문제설명

• 주어진 파라미터: String[] friends, String[] gifts
• return: 다음달에 선물을 가장 많이 받을 사람의 선물 수
• 선물을 받는 규칙 (A, B)
  • A가 B보다 지난달에 선물을 많이 줬을 경우 다음달에 B가 A에게 선물을 1개 준다
  • A와 B가 선물을 주고받지 않았거나 같은 수의 선물을 줬을 경우 선물 지수를 비교해 선물지수가 작은 사람이 선물 지수가 큰사람에게 선물을 준다.
    • 선물지수? 선물을 준 횟수 - 선물을 받은 횟수
    • 선물지수가 같을 경우 선물을 주고받지 않는다.
• friends는 친구의 이름 배열 → 중복된 이름은 없다.
• gifts는 선물을 주고받은 기록 [”준사람 받은사람”]
  
  

풀이방식

1. gifts 배열은 지난달의 기록들이다 → 누가 얼마나 줬는지, 누가 얼마나 받았는지를 기록해야한다.
2. 내가 필요한게 뭔가: 지난달 친구들이 주고받은 행렬과 선물지수
3. 행렬로 표시하면 어떨까 → from to 로 gifts를 받아서 행렬에 +1 시키기
4. 행렬의 행의 합은 준 합, 열의 합은 받은 합 → 둘의 차는 선물지수
5. history[from][to]와 history[to][from] 비교해서 더 적게 준 쪽이 많이 준쪽에 하나 추가
   → 결과를 추가할 배열 필요
   → 선물 지수를 추가할 배열 필요
   
   

코드

class Solution {
    public int solution(String[] friends, String[] gifts) {

        // 선물 주고받은 횟수 저장
        int len = friends.length;
        int[][] historys = new int[len][len];

        // 결과 저장용
        int[] answer = new int[len];

        // 선물 지수를 저장
        int[] points = new int[len];

        // 1. gifts 배열을 통해서 주고받은 기록을 history에 넣기 (friends에 저장된 인덱스로 history에 저장돼야함)
        for(String gift : gifts){
            String[] history = gift.split(" ");
            // history = [from, to] -> friends 에서 index값 찾기
            int from = 0;
            int to = 0;

            for(int i = 0; i < len; i++){
                if(friends[i].equals(history[0])){
                    from = i;
                }
                if(friends[i].equals(history[1])){
                    to = i;
                }
            }

            historys[from][to] += 1;

        }

        // 2. 행렬을 가지고 선물지수 구하기
        for(int i = 0; i < len; i++){
            int give = 0;
            int take = 0;

            for (int j = 0; j < len; j++) {
                give += historys[i][j];
            }

            for (int j = 0; j < len; j++) {
                take += historys[j][i];
            }

            int count = give - take;
            points[i] = count;
        }

        // 3. 비교하기 = 받는 횟수 구하기
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i == j) continue;

                int give = historys[i][j];
                int take = historys[j][i];

                if (give > take) {
                    answer[i]++; // 선물을 더 적게 준 경우
                } else if (give == take) {
                    // 선물 지수를 기준으로 비교
                    if (points[i] > points[j]) {
                        answer[i]++;
                    }
                }
            }
        }

        int max = 0;
        for(int i : answer){
            if( i > max){
                max = i;
            }
        }

        return max;
    }

}

알게된 점

1. 자바의 문자열 배열은 순서대로 저장된 데이터 집합으로 데이터를 저장하거나 특정 인덱스에 접근하는 기능만 제공한다

   → 특정 요소의 위치를 찾는 기능은 제공되지 않는다.(List에서만 제공)

1. str의 split(기준점)을 통해 배열로 반환 받을 수 있다.

---

풀이과정이 헷갈려서 시간이 오래 걸렸지만 풀고 나니 재밌었다!

참 쉽쥬잉?