문제

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

풀이

친구 목록과 친구들 사이 주고 받은 기록이 주어졌을 때 문제에 주어진 조건에 따라 선물을 가장 많이 받는 사람의 선물 개수를 출력하는 문제이다.

가장 먼저 친구들의 목록이 주어졌는데 이를 Index로 사용하기 위해 HashMap<>을 통해
이름에 대한 번호를 임의로 지정해주었다.

HashMap<String, Integer> nameNumber = new HashMap<>();
for(int i = 0 ; i < friends.length;i++){
       nameNumber.put(friends[i], i);
}

다음에 구해야 할 것은 친구들 사이 선물을 주고 받은 내역이다.

muzi가 frodo에게 준 선물은 2개라는 의미이며 이를 그래프 형태로 나타내었다.

선물 지수는 (보낸 선물의 개수 - 받은 선물의 개수) 이므로 그래프를 형성할 때 다음과 같이 선물 지수도 바로 구할 수 있다.

for(int i = 0 ; i < gifts.length;i++){
            String[] names = gifts[i].split(" ");
            int giveNumber = nameNumber.get(names[0]); // 준 사람
            int receiveNumber = nameNumber.get(names[1]); // 받은 사람
            presentScore[giveNumber]++; //준 사람은 선물지수 + 1
            presentScore[receiveNumber]--; // 받은 사람은 선물지수 -1

            graph[giveNumber][receiveNumber]++; // 선물 관계도 업데이트
}

친구들 사이의 선물 관계도를 graph를 나타내고, 선물 지수도 구하였으면 이제 주어진 조건에 따라 받을 선물의 개수를 구해주면 된다.

for(int i = 0 ; i < N  - 1; i++){
            for(int j = i + 1;j < N ;j++){
                if(graph[i][j] > graph[j][i]){ // i가 j보다 선물 준 개수가 많을 때
                    totalPresent[i]++;
                }
                else if(graph[i][j] < graph[j][i]){ // j가 i보다 선물 준 개수가 많을 때
                    totalPresent[j]++;
                }
                else{ // 준 선물이 같을 때 선물 지수 비교
                    if(presentScore[i] > presentScore[j]){
                        totalPresent[i]++;
                    }
                    else if(presentScore[i] < presentScore[j]){
                        totalPresent[j]++;
                    }
                    //선물 지수가 같다면 아무도 못 받음
                }
            }
        }

문제 조건은 별로 어렵지 않았지만 번호가 아닌 String으로 배열을 넘겨주어 숫자 index로 바꾸는 과정에서 헷갈렸었다. 문제를 제대로 파악하고 정확한 구현하기 좋은 문제였다.

전체 코드

import java.util.HashMap;

public class Main {

    int[][] graph = new int[51][51];
    int[] presentScore = new int[51];
    int[] totalPresent = new int[51];

    HashMap<String, Integer> nameNumber = new HashMap<>();
    int N; // 친구 수

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

        N = friends.length;
        for(int i = 0 ; i < N;i++){
            nameNumber.put(friends[i], i);
        }

        for(int i = 0 ; i < gifts.length;i++){
            String[] names = gifts[i].split(" ");
            int giveNumber = nameNumber.get(names[0]); // 준 사람
            int receiveNumber = nameNumber.get(names[1]); // 받은 사람
            presentScore[giveNumber]++; //준 사람은 선물지수 + 1
            presentScore[receiveNumber]--; // 받은 사람은 선물지수 -1

            graph[giveNumber][receiveNumber]++; // 선물 관계도 업데이트
        }

        for(int i = 0 ; i < N  - 1; i++){
            for(int j = i + 1;j < N ;j++){
                if(graph[i][j] > graph[j][i]){ // i가 j보다 선물 준 개수가 많을 때
                    totalPresent[i]++;
                }
                else if(graph[i][j] < graph[j][i]){ // j가 i보다 선물 준 개수가 많을 때
                    totalPresent[j]++;
                }
                else{ // 준 선물이 같을 때 선물 지수 비교
                    if(presentScore[i] > presentScore[j]){
                        totalPresent[i]++;
                    }
                    else if(presentScore[i] < presentScore[j]){
                        totalPresent[j]++;
                    }
                    //선물 지수가 같다면 아무도 못 받음
                }
            }
        }

        int answer = totalPresent[0];
        for(int i = 1 ; i < N ; i++){
            answer = Math.max(answer,totalPresent[i]);
        }

        return answer;
    }

    public static void main(String[] args) {
        String[] friends = {"joy", "brad", "alessandro", "conan", "david"};
        String[] gifts = {"alessandro brad", "alessandro joy", "alessandro conan", "david alessandro", "alessandro david"};
        int res = new Main().solution(friends, gifts);
        System.out.println(res);
    }
}