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

📌 문제

프로그래머스

📌 풀이

처음에는 HashMap으로 풀어보려다가 준 선물, 받은 선물, 선물 지수만 map에 넣고 헤맸다. 선물을 주고 받은 기록을 어떻게 비교할 지 감이 오지 않았다.  결국 정답 코드를 보고 이해한 후 다시 분석해 정리해보았다.

 

먼저 문제의 규칙을 요약하자면 다음과 같다.

• 선물을 주고 받은 적이 있고, 주고 받은 수가 다르다면
  • 더 많은 선물을 준 사람이 선물을 받는다.
• 선물을 주고 받은 적이 없거나, 주고 받은 수가 같다면
  • 선물 지수(준 선물 수 - 받은 선물 수)를 비교해 선물 지수가 큰 사람이 선물을 받는다.
  • 선물 지수도 같다면 선물을 주고 받지 않는다.

그리고나서 HashMap과 int형 배열을 이용해 풀었다.

• HashMap map : 이름과 인덱스를 저장하는 HashMap, friends 배열을 순회하며 저장한다.
• int[] giftScore : 선물 지수를 저장하는 배열, friends 배열의 인덱스 순으로 선물 지수가 저장된다.
• int[][] record : 선물을 주고 받은 내역을 저장하는 배열, 예를 들어 record[0][1]은 friends[0]의 사람이 friends[1]의 사람에게 준 선물의 개수가 저장된다.

내가 구현을 어려워한 부분은 다음과 같다. record 배열의 index를 서로 바꾸면 준 사람과 받은 사람을 비교할 수 있다는 사실을 생각하지 못했다. 물론 위에 적은 것과 같이 map과 배열들을 선언해놓고나면 쉽게 떠올렸을 수도 있겠지만 그것부터 쉽지 않았다는 점..아무튼 문제 규칙에 따라 조건문을 작성한 후 count의 최댓값을 갱신해주며 for문을 돌리면 다음달에 가장 많은 선물을 받는 친구가 받을 선물의 수를 구할 수 있다.

int answer = 0;
for (int i = 0; i < friends.length; i++) {
    int count = 0;
    for (int j = 0; j < friends.length; j++) {
        if (i == j) continue;
        if (record[i][j] > record[j][i]) count++;
        else if (record[i][j] == record[j][i] && giftScore[i] > giftScore[j]) count++;
    }
    answer = Math.max(count, answer);
}

 

📌 전체 코드

import java.util.*;

class Solution {
    public 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); // 이름과 인덱스를 저장하는 HashMap
        }
        
        int[] giftScore = new int[friends.length]; // 선물 지수를 저장하는 배열
        int[][] record = new int[friends.length][friends.length]; // 선물을 주고받은 기록을 저장하는 배열
        
        for (String gift : gifts) {
            String[] names = gift.split(" ");
            String give = names[0];
            String take = names[1];
            
            giftScore[map.get(give)]++;
            giftScore[map.get(take)]--;
            record[map.get(give)][map.get(take)]++;
        }
        
        int answer = 0;
        for (int i = 0; i < friends.length; i++) {
            int count = 0;
            for (int j = 0; j < friends.length; j++) {
                if (i == j) continue;
                if (record[i][j] > record[j][i]) count++;
                else if (record[i][j] == record[j][i] && giftScore[i] > giftScore[j]) count++;
            }
            answer = Math.max(count, answer);
        }
        
        return answer;
    }
}