[2024 KAKAO INTERN] 가장 많이 받은 선물

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

프로그래머스

 

문제 유형

구현

 

문제 난이도

Lev1

 

문제 분석

1. 선물을 주고 받은 기억이 있는 경우, 더 많이 준 사람이 다음달에 받는다.
2. 주고 받지 않았다면 선물 지수를 통해 선물을 받는다.
3. 만약 서로 준 횟수가 동일한 경우, 선물지수가 더 큰 사람이 선물을 받는다. (선물 지수가 동일한 경우는 서로 주고 받지 않는다.)
4. 가장 많이 받는 친구의 선물의 개수를 출력한다.

문제는 지문에 나온 내용을 토대로 예시에서 주어진 테이블과 동일하게 배열을 만들어서 처리하면 쉽게 풀 수 있다.

 

코드 분석

 

HashMap을 통하여, 친구의 이름과 인덱스를 매칭시킨다. arr[][] 에는 행에는 준 사람, 열에는 받은 사람으로 배열을 만들어, 문제와 동일하게 선물을 준 횟수를 counting한다.

int N = friends.length;
Map<String, Integer> map = new HashMap<>();
int[][] arr = new int[N][N];

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

int A, B;
for(int i = 0; i < gifts.length; i++) {

    A = map.get(gifts[i].split(" ")[0]);
    B = map.get(gifts[i].split(" ")[1]);

    arr[A][B]++;
}

 

선물 지수 = 준 선물의 횟수 - 받은 선물의 횟수

int[] points = new int[N];

for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
        points[i] += arr[i][j];
        points[j] -= arr[i][j];
    }
}

 

준 선물이 받은 선물보다 많은 경우를 비교해, 준 선물이 많은 경우 다음 달 선물에 추가하고, 반대로 받은 선물이 많은 경우, 준 사람에게 선물을 제공한다. 또한 주고 받은 횟수가 동일하거나, 서로 주고 받지 않은 경우, 선물 지수를 비교하고, 선물지수까지 동일한 경우, 주고 받지 않는다.

 int[] res = new int[N];
for(int i = 0; i < N; i++) {
    for(int j = i + 1; j < N; j++) {
        if(arr[i][j] > arr[j][i]) res[i]++;
        else if(arr[i][j] < arr[j][i]) res[j]++;
        else {
            if(points[i] > points[j]) res[i]++;
            else if(points[i] < points[j]) res[j]++;
        }       
    }
}

 

전체 코드

import java.util.*;
import java.io.*;

/**
* 선물을 주고 받은 기억이 있는 경우, 더 많이 준 사람이 다음달에 받는다.
* 주고 받지 않았다면 선물 지수를 통해 선물을 받는다.
* 만약 서로 준 횟수가 동일한 경우, 선물지수가 더 큰 사람이 선물을 받느다.

* 가장 많이 받는 친구의 선물의 개수를 출력한다.
*/

class Solution {
    public int solution(String[] friends, String[] gifts) {
        
        int N = friends.length;
        Map<String, Integer> map = new HashMap<>();
        int[][] arr = new int[N][N];
        
        for(int i = 0; i < N; i++) {
            map.put(friends[i], i);
        }
        
        int A, B;
        for(int i = 0; i < gifts.length; i++) {
            
            A = map.get(gifts[i].split(" ")[0]);
            B = map.get(gifts[i].split(" ")[1]);
            
            arr[A][B]++;
        }
        
        int[] points = new int[N];
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                points[i] += arr[i][j];
                points[j] -= arr[i][j];
            }
        }
        
        int[] res = new int[N];
        for(int i = 0; i < N; i++) {
            for(int j = i + 1; j < N; j++) {
                if(arr[i][j] > arr[j][i]) res[i]++;
                else if(arr[i][j] < arr[j][i]) res[j]++;
                else {
                    if(points[i] > points[j]) res[i]++;
                    else if(points[i] < points[j]) res[j]++;
                }       
            }
        }
        
        int max = 0;
        
        for(int i = 0; i < N; i++) if(max < res[i]) max = res[i];
        
        return max;
    }
}