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

문제

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

프로그래머스

생각

1. 주고받은거 배열 인덱스가 있으니,, 이차원 배열을 만들어 누가 누구한테 얼만큼 줬는지 기록하기
2. 순차 배열을 순회하며 서로 선물을 받았는가? 안받았는가 체크
2.1 받았다면 이차원배열 더 높은 사람이 결과 ++ 
2.2 주고 받은적 없거나, 정확히 같은 수로 선물 주고받았을 경우
2.2.1 선물지수로 판단하기 
- 가로 합 : 준 선물, 세로 합 : 받은 선물 = 가로합 - 세로 합 = 선물지수 
- 선물지수가 큰 사람 결과 ++
2.2.1.1 선물지수도 같다면 아무도 ++ X

코드

public class Main {
    public static void main(String[] args) {
        System.out.println(solution(new String[]{"muzi", "ryan", "frodo", "neo"}, new String[]{"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"}));
        System.out.println(solution(new String[]{"joy", "brad", "alessandro", "conan", "david"}, new String[]{"alessandro brad", "alessandro joy", "alessandro conan", "david alessandro", "alessandro david"}));
        System.out.println(solution(new String[]{"a", "b", "c"}, new String[]{"a b", "b a", "c a", "a c", "a c", "c a"}));
    }

    public static int solution(String[] friends, String[] gifts) {
        int answer = 0;
        // 1. 주고받은거 배열 인덱스가 있으니,, 이차원 배열을 만들어 누가 누구한테 얼만큼 줬는지 기록하기
        int [][] info = new int[friends.length][friends.length];
        for(String el : gifts){
            String A = el.split(" ")[0];
            String B = el.split(" ")[1];

            int idx1 = findIdx(friends,A);
            int idx2 = findIdx(friends,B);

            info[idx1][idx2]++;
        }
        int [] result = new int [friends.length];
        // 2. 순차 배열을 순회하며 서로 선물을 받았는가? 안받았는가 체크
        for (int i = 0; i < friends.length; i++) {
            for (int j = 0; j < friends.length; j++) {
                if(i==j)continue;
                if(info[i][j]!=0 || info[j][i]!=0){
                    // 2.1 서로 선물을 받은 경우 이차원 배열 더 높은 사람이 결과 ++
                    int AVal = info[i][j];
                    int BVal = info[j][i];
                    if(AVal>BVal){
                        result[i]++;
                    }else if(AVal<BVal){
                        result[j]++;
                    }else{
                        // 2.2 정확히 같은 수로 선물 주고받았을 경우
                        int iJisu = jisu(i,info);
                        int jJisu = jisu(j,info);
                        if(iJisu>jJisu){
                            result[i]++;
                        }else if(iJisu<jJisu){
                            result[j]++;
                        }else{
                            // 2.2.1.1 선물지수도 같다면 아무도 ++ X
                        }
                    }
                }else{
                    // 2.2 주고 받은적 없거나
                    int iJisu = jisu(i,info);
                    int jJisu = jisu(j,info);
                    if(iJisu>jJisu){
                        result[i]++;
                    }else if(iJisu<jJisu){
                        result[j]++;
                    }else{
                        // 2.2.1.1 선물지수도 같다면 아무도 ++ X
                    }
                }
            }
        }
        int max_val = -1;
        for (int i = 0; i < result.length; i++) {
            max_val = Math.max(max_val,result[i]);
        }
        // A->B, B->A 중복 계산되었으니 /2 하기
        return max_val / 2;
    }

    private static int jisu(int i, int[][] info) {
        // 2.2.1 가로 합 : 준 선물, 세로 합 : 받은 선물
        // 가로합 - 세로 합 = 선물지수
        // 선물지수가 큰 사람 결과 ++ 하기 위한 IDX 반환
        int gSum = garoSum(i,info[i]);
        int sSum = seroSum(i,info);
        return gSum-sSum;
    }
    private static int garoSum(int i, int[] info) {
        int sum = 0;
        for (int j = 0; j < info.length; j++) {
            sum+=info[j];
        }
        return sum;
    }

    private static int seroSum(int i, int[][] info) {
        int sum = 0;
        for (int j = 0; j < info.length; j++) {
            sum += info[j][i];
        }
        return sum;
    }
    private static int findIdx(String[] friends, String a) {
        for (int i = 0; i < friends.length; i++) {
            if(friends[i].equals(a)){
                return i;
            }
        }
        return -1;
    }
}

 

• 제출하고보니 맞았는데,, 중복이 있어 리팩토링함

// 2. 순차 배열을 순회하며 서로 선물을 받았는가? 안받았는가 체크
for (int i = 0; i < friends.length; i++) {
    for (int j = 0; j < friends.length; j++) {
        if(i==j)continue;
        if((info[i][j]==0 && info[j][i]==0) || (info[i][j] == info[j][i])){
            // 2.2 주고 받은적 없거나 주고 받은 선물 갯수가 같은 경우
            int iJisu = jisu(i,info);
            int jJisu = jisu(j,info);
            if(iJisu>jJisu){
                result[i]++;
            }else if(iJisu<jJisu){
                result[j]++;
            }else{
                // 2.2.1.1 선물지수도 같다면 아무도 ++ X
            }
        }else{
            // 2.1 서로 선물을 받은 경우 이차원 배열 더 높은 사람이 결과 ++
            int AVal = info[i][j];
            int BVal = info[j][i];
            if(AVal>BVal){
                result[i]++;
            }else if(AVal<BVal){
                result[j]++;
            }
        }
    }
}

다른 사람 코드

• 이 코드는 설명에 완벽하게 가깝게 코드를 짜고, 해설 의도를 이해하여 작성한 것 같다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        System.out.println(solution(new String[]{"muzi", "ryan", "frodo", "neo"}, new String[]{"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"}));
        System.out.println(solution(new String[]{"joy", "brad", "alessandro", "conan", "david"}, new String[]{"alessandro brad", "alessandro joy", "alessandro conan", "david alessandro", "alessandro david"}));
        System.out.println(solution(new String[]{"a", "b", "c"}, new String[]{"a b", "b a", "c a", "a c", "a c", "c a"}));
    }

    public static int solution(String[] friends, String[] gifts) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < friends.length; i++) {
            map.put(friends[i], i);
        }
        int[] index = new int[friends.length];  // 선물지수
        int[][] record = new int[friends.length][friends.length];

        for (String str : gifts) {
            String[] cur = str.split(" ");
            index[map.get(cur[0])]++;   // 준사람 더하고
            index[map.get(cur[1])]--;   // 받은사람 빼고
            record[map.get(cur[0])][map.get(cur[1])]++; // 기록하고
        }

        int ans = 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 (record[i][j] > record[j][i]) cnt++; // 무지가 선물 더 줬으면 선물을 받아야하니까 cnt++
                else if (record[i][j] == record[j][i] && index[i] > index[j]) cnt++; // 같다면 선물지수가 더 높다면 cnt++
            }
            ans = Math.max(cnt, ans);
        }
        return ans;
    }
}