[프로그래머스] (2024 KAKAO WINTER INTERNSHIP) 가장 많이 받은 선물 / 자바(Java)

• 문제

• 해설

• 주의점

• 코드

문제

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

프로그래머스

 

---

해설

선물을 주고 받은 기록을 정리하고 그 기록을 바탕으로 이번에 선물을 최대로 많이 받은 사람의 선물 수를 구하는 문제입니다.

 

선물기록을 2차원 배열로 정리하여 이번에 선물을 받는 경우를 쉽게 구하도록 하는 것이 이번 문제의 요점인듯 싶습니다.

 

friends의 입력값이 모두 문자열 이기 때문에 각 문자열에 대응하는 이름을 빠르게 찾기 위해 Map을 사용해 이름들을 들어오는 순으로 숫자를 대응시켜 주었습니다. a, b, c로 들어왔다면 2차원 배열에서 사용하기 편하도록 각각 0, 1, 2로 사용될 것 입니다.

 

gifts를 split함수를 사용해 나누어 선물의 교환 기록을 저장하는 record[][]배열에 입력합니다. 각 record[i][j]는 i가 j에게 준 선물의 수를 의미하므로 gifts의 한 값별로 record에 하나씩 값을 더해줍니다.

 

record에 기록들을 정리해 저장했으므로 선물 지수를 미리 계산해 줍니다. 선물지수는 자신이 준 선물수에서 받은 선물수를 뺀 수이므로 giftNum[i] = record[i][모든 친구들] - record[모든친구들][i]로 표현 가능합니다.record의 2차원 배열로 보면 i행의 총합 - i열의 총합으로 간단히 사용해 줍니다.

 

최종적으로 이번 주에 주고받을 선물을 계산합니다.

이번 주에 주고 받을 선물은 지금까지 준 선물과 받은 선물에 기반하여 계산하기 때문에 record[i][j]와 record[j][i]를 비교해 줍니다. 이렇게 되면 2차원 배열의 절반만 탐색하면 모든 값을 확인 가능하므로 2중 for문을 생성할 때 i는 0~전체 친구 수, j는 i+1에서 전체 친구 수로 두어 좌하단 반쪽을 탐색합니다.

 

1. 두 사람이 선물을 주고 받은 기록이 없거나 주고 받은 수가 같다면

이 조건에서 선물을 주고 받은 기록이 없는 경우는 둘다 0 인경우이므로 record[i][j] == record[j][i] 인 조건 하나로 해결가능하다.

이때 선물지수에 따라 더 많은 쪽이 선물을 가져갑니다.

 

2. 두 사람이 선물을 주고받은 경우.

record의 값을 기반으로 더 많은 선물을 준 사람의 thisWeek에 1을 추가합니다.

 

thisWeek배열에 들어있는 값중 가장 큰 값을 answer에 저장해주어 해결할 수 있습니다.

주의점

• 선물지수가 같은 경우 누구도 선물을 받아갈 수 없다.

---

코드

import java.util.*;
class Solution {

    public int solution(String[] friends, String[] gifts) {
        int answer = 0;
        
        // nameTag에 각 이름을 임의의 숫자로 치환해 저장
        Map<String, Integer> nameTag = new HashMap<>();
        for(int i=0;i<friends.length;i++){
            nameTag.put(friends[i],i);
        }
        
        // 이번달까지 선물의 교환기록(recode[i][j] 는 i가 j에게 준 선물의 수)
        int[][] record = new int[friends.length][friends.length];
        for(String gift : gifts){
            String[] names = gift.split(" ");
            record[nameTag.get(names[0])][nameTag.get(names[1])]++;
        }
        
        // 선물지수 
        int[] giftNum = new int[friends.length];
        for(int i=0;i<friends.length;i++){
            for(int j=0;j<friends.length;j++){
                giftNum[i] += (record[i][j]-record[j][i]);
            }
        }
        
        // 이번주 주고 받을 선물
        int[] thisWeek = new int[friends.length];
        for(int i=0;i<friends.length;i++){
            for(int j=i+1;j<friends.length;j++){
                if(record[i][j]==record[j][i]){
                    // 선물지수 비교 (같다면 추가 없음)
                    if(giftNum[i]>giftNum[j]) thisWeek[i]++;
                    else if(giftNum[i]<giftNum[j])thisWeek[j]++;
                }else{
                    thisWeek[record[i][j]>record[j][i] ? i : j]++;
                }
            }
        }
        
        for(int num : thisWeek){
            answer = Math.max(num,answer);
        }
        return answer;
    }
}