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

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

프로그래머스

 

1. 문제 설명

- 변수

friends : 친구들의 이름

gifts : "선물을 준 사람, 선물을 받은 사람"

 

- 결과

다음달에 가장 많이 받은 선물의 수

 

- 주의사항

• 선물을 더 많이 준 사람이 다음 달에 선물을 하나 더 받는다.
• 주고 받은 선물이 같거나 없다면 선물지수가 더 작은 사람에게 선물을 하나 받는다.
• 선물 지수가 같다면 다음 달에 선물을 주고받지 않는다.

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

 

2. 풀이 과정

처음엔 Map만 사용하여 입출력에 나온 테이블을 만들려고하다가 꼬여서 풀지 못했는데, 해답을 참고하니 처음에 친구의 인덱스를 map에 넣어 인덱스로 만들고 1차원과 2차원배열에 사용하여 풀어가는 과정이 있었다.

 

- 친구들 인덱스를 Map에 지정한다. (friendIndex)

        int answer = 0;
        int friend_len = friends.length;
        HashMap<String, Integer> friendIndex = new HashMap<>(); // 친구 인덱스
        // 친구 인덱스 지정
        for (int i = 0; i < friend_len; i++) {
            friendIndex.put(friends[i], i);
        }

muzi : 0

ryan : 1

frodo : 2

neo : 3

 

 

- 선물 지수와 주고받은 선물 테이블을 그린다.

        int[][] Table = new int[friend_len][friend_len];
        int[] giftNumber = new int[friend_len]; // 선물 지수
        for (String gift : gifts) {
            String[] giftInfo = gift.split(" "); 
            // giftInfo[0] : 선물을 준 친구
            // giftInfo[1] : 선물을 받은 친구
            
            // 주고받은 선물 테이블
            Table[friendIndex.get(giftInfo[0])][friendIndex.get(giftInfo[1])]++;
            // 선물 지수
            giftNumber[friendIndex.get(giftInfo[0])]++; // 선물을 준 친구 +1
            giftNumber[friendIndex.get(giftInfo[1])]--; // 선물을 받은 친구 -1
        }

 

- 주고받은 선물 테이블 (Table)

↓준 사람 \ 받은 사람 →	muzi (0)	ryan (1)	frodo (2)	neo (3)
muzi (0)	-	0	2	0
ryan (1)	3	-	0	0
frodo (2)	1	1	-	0
neo (3)	1	0	0	-

 

- 선물지수(giftNumber)

muzi (0)	ryan (1)	frodo (2)	neo (3)
-3	2	0	1

 

 

- 주고받은 선물 테이블(2차원)로 친구마다 선물준 적이 많을 경우 or 동일할때 선물지수가 높을 경우를 비교하여 다음달에 받을 가장 많은 선물의 갯수를 갱신한다.

        // 친구마다 선물 비교
        for (int i = 0; i < friend_len; i++) {
            int count = 0; // 다음달에 받는 선물의 수
            for (int j = 0; j < friend_len; j++) {
                // 본인일 경우 빼기
                if(i == j){
                    continue;
                }
                // (선물 준 적이 더 많을 경우) or (동일할 때, 선물지수가 높을 경우)
                if(Table[i][j] > Table[j][i] || (Table[i][j] == Table[j][i] && giftNumber[i] > giftNumber[j])) {
                    count++; // 선물 하나 더 받기
                }
                // 다음달에 받을 선물을 비교해서 높은 것을 저장
                answer = answer > count ? answer : count;
            }
        }
        
        return answer;

 

- 전체 코드

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int answer = 0;
        int friend_len = friends.length;
        HashMap<String, Integer> friendIndex = new HashMap<>(); // 친구 인덱스
        int[][] graph = new int[friend_len][friend_len]; // 주고 받은 선물 그래프
        int[] giftNumber = new int[friend_len]; // 선물 지수
        
        // 친구 인덱스 지정
        for (int i = 0; i < friend_len; i++) {
            friendIndex.put(friends[i], i);
        }

        for (String gift : gifts) {
            String[] giftInfo = gift.split(" "); 
            // giftInfo[0] : 선물을 준 친구
            // giftInfo[1] : 선물을 받은 친구
            
            // 주고받은 선물 그래프
            graph[friendIndex.get(giftInfo[0])][friendIndex.get(giftInfo[1])]++;
            // 선물 지수
            giftNumber[friendIndex.get(giftInfo[0])]++; // 선물을 준 친구 +1
            giftNumber[friendIndex.get(giftInfo[1])]--; // 선물을 받은 친구 -1
        }
        
        // 친구마다 선물 비교
        for (int i = 0; i < friend_len; i++) {
            int count = 0; // 다음달에 받는 선물의 수
            for (int j = 0; j < friend_len; j++) {
                // 본인일 경우 빼기
                if(i == j){
                    continue;
                }
                // (선물 준 적이 더 많을 경우) or (동일할 때, 선물지수가 높을 경우)
                if(graph[i][j] > graph[j][i] || (graph[i][j] == graph[j][i] && giftNumber[i] > giftNumber[j])) {
                    count++; // 선물 하나 더 받기
                }
                // 받은 선물을 비교해서 높은 것을 저장
                answer = answer > count ? answer : count;
            }
        }
        
        return answer;
    }
}