[JAVA] 프로그래머스 : 가장 많이 받은 선물 문제 풀이 | Map과 ArrayList

2024 KAKAO WINTER INTERNSHIP: 가장 많이 받은 선물 문제 풀이 

코딩테스트 연습 | 프로그래머스 스쿨

 

🔒 문제

선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.

두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.
예를 들어 A가 B에게 선물을 5번 줬고, B가 A에게 선물을 3번 줬다면 다음 달엔 A가 B에게 선물을 하나 받습니다.

두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.
선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값입니다.
예를 들어 A가 친구들에게 준 선물이 3개고 받은 선물이 10개라면 A의 선물 지수는 -7입니다. 
B가 친구들에게 준 선물이 3개고 받은 선물이 2개라면 B의 선물 지수는 1입니다. 
만약 A와 B가 선물을 주고받은 적이 없거나 정확히 같은 수로 선물을 주고받았다면, 
다음 달엔 B가 A에게 선물을 하나 받습니다.

만약 두 사람의 선물 지수도 같다면 다음 달에 선물을 주고받지 않습니다.

위에서 설명한 규칙대로 다음 달에 선물을 주고받을 때, 당신은 선물을 가장 많이 받을 친구가 받을 선물의 수를 알고 싶습니다.

친구들의 이름을 담은 1차원 문자열 배열 friends 이번 달까지 친구들이 주고받은 선물 기록을 담은 1차원 문자열 배열 gifts가 매개변수로 주어집니다. 이때, 다음 달에 가장 많은 선물을 받는 친구가 받을 선물의 수를 return 하도록 solution 함수를 완성해 주세요.

 

---

🔎  풀이

문제 주제가 친근하고 설명이 무척 친절해서 쉽게 접근할 수 있는 문제였다. 이 문제를 풀기 위해선 세 개의 자료 구조가 필요한데 나는 다차원 배열 한 개와 해시맵 두 개를 사용했다. 오랜만에 두 개의 자료 구조를 사용하면서 중요한 메서드를 복습할 수 있었다.

문제 자체에서 두 가지 자료 구조에 대한 힌트를 제공해 줘서 더욱 수월하게 풀이할 수 있었다.

 

내 풀이 로직은 다음과 같다.

1.  먼저 주어진 gift 배열을 사용해서 각 사용자가 받은 선물을 나타내는 다차원 배열 giftRecordList와 각 사용자의 선물 지수를 저장하는 맵 giftQuotienMap을 채운다. 

 

다음 예시는 주어진 gift, friends 배열이 다음과 같이 주어졌을 때를 기준으로 작성했다.

String[] friends = {"muzi", "ryan", "frodo", "neo"};
String[] gifts = {"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"};

 

첫 번째 for문을 거친 giftRecordList와 giftQuotienMap은 다음과 같다.

 

🔹 giftRecordList

준 사람 \ 받은 사람	muzi	ryan	frodo	neo
muzi	-	0	2	0
ryan	3	-	0	0
frodo	1	1	-	0
neo	1	0	0	-

 

🔹 giftQuotienMap

KEY	ryan	muzi	neo	frodo
VALUE	2	-3	1	0

 

 

2. 필요한 리스트와 맵을 모두 채운 다음엔 완성한 두 개를 활용해서 다음 달에 각 사용자가 받을  선물 개수를 계산한다.

우선 for문을 구성할 때는 giftRecordList의 행 즉 선물을 준 사람을 본인으로 두고 로직을 짰다. 그리고 상대와 비교했을 때 본인이 준 선물 개수가 더 크거나 선물 지수가 큰 경우에만 giftPredictedMap의 값을 +1 해주도록 한다.

 

giftRecordList에서 대각선을 기준으로 서로 주고받은 사용자가 대칭이 되므로, 

giftRecordList [본인][상대]와 giftRecordList [상대][본인]을 비교한다. 만약 전자가 크다면 본인이 크므로 deserve = true.

상대가 더 큰 경우는 고려하지 않는다. 그건 상대방이 본인이 되는 경우에 고려할 것이므로 중복이 일어나지 않도록 고려하지 않았다.

 

만약 서로 주고받은 선물이 같은 경우, 선물 지수를 비교해야 한다.

선물 지수를 비교했을 때 내 선물 지수가 더 크다면 deserve= true

 

그리고 for문의 끝단에서 deserve가 true인 경우 다음 달에 받을 선물 개수를 +1 한 값으로 갱신한다.

이렇게 for 문을 돌면 giftPredictedMap은 다음과 같이 갱신된다.

 

🔹 giftPredictedMap

KEY	ryan	muzi	neo	frodo
VALUE	2	1	2	1

 

이렇게 선물 개수를 갱신하고 나면, giftPredictedMap에서 Max value값은 2이다. 

 

🔎  배운 내용

1. friends 배열에서 특정한 사용자 이름이 몇 번째 인덱스인지 가져오고 싶었는데 배열에서는 인덱스를 찾아오는 메서드가 없었다.

대신 해당 배열을 List로 변환하면 리스트에는 indexOf 메서드가 있기 때문에 쉽게 가져올 수 있다.

List<String> friendsList = Arrays.asList(friends);

 

위와 같이 Arrays.asList를 사용해서 배열을 리스트로 변환하고 변환한 리스트를 사용함으로써 고민을 해결했다.

 

2. Map에서 최댓값을 찾는 방법: Collections 패키지 사용

Collections.max(giftPredictedMap.values())

 

 

🔑 출력문이 함께 있는 풀이

Solution.java

import java.util.*;


class Solution {
    static int[][] giftRecordList;                 // 받은 선물 개수 나타내는 다차원 배열

    static Map<String,Integer> giftQuotientMap;    // 각 사용자의 선물 지수

    static Map<String,Integer> giftPredictedMap;   // 각 사용자가 다음 달에 받을 선물 개수


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

        List<String> friendsList = Arrays.asList(friends);

        // 선물 기록 리스트 초기화
        giftRecordList = new int[friends.length][friends.length];

        // 선물 지수 맵 초기화
        giftQuotientMap = new HashMap<>();
        for( String friend : friends ) giftQuotientMap.put(friend, 0);

        // 다음 달에 받을 선물 개수 맵 초기화
        giftPredictedMap = new HashMap<>();
        for( String friend : friends ) giftPredictedMap.put( friend, 0 );

		// 1. giftRecordList, giftQuotienMap 채우기
        for( String gift : gifts ){

            // [1] 문자열 띄어쓰기 기준으로 나누기
            String[] result = gift.split(" ");


            // [2] 선물 지수 값 갱신하기
            int giver = giftQuotientMap.get( result[0] );        // 선물 준 사람은 +1
            giftQuotientMap.replace( result[0], giver + 1 );

            int receiver = giftQuotientMap.get( result[1] );     //  선물 받은 사람은 -1
            giftQuotientMap.replace( result[1], receiver - 1 );


            // [3]  선물 받은 개수 리스트 값 갱신하기
            int giverIndex = friendsList.indexOf(result[0]);
            int receiverIndex = friendsList.indexOf(result[1]);
            giftRecordList[giverIndex][receiverIndex] += 1 ;

        }

        // 선물 리스트 출력해보기
        System.out.println("선물 리스트");
        for( int i = 0; i < friends.length; i++ ){
            for(int j = 0; j < friends.length; j++){
                System.out.print(giftRecordList[i][j] + " ");
            }
            System.out.println();
        }
        // 선물 지수 출력
        System.out.println("선물 지수");
        for( Object o : giftQuotientMap.entrySet() ){
            System.out.print( o.toString() + " ");
        }
        System.out.println();


        // 2. 다음 달에 받을 선물 개수 계산하기 giftPredictedMap
        for( String friend : friends ){
            for( int i = 0; i < friends.length; i++ ){

                int friendIndex = friendsList.indexOf(friend);
                String targetFriend = friendsList.get(i);       // 비교 대상인 상대방
                boolean deserve = false;

                if(friendIndex == i) continue;      // 본인 제외
                else if(giftRecordList[friendIndex][i] > giftRecordList[i][friendIndex]){
                    // 내가 준 선물 개수가 더 많을 경우 내가 받을 선물 개수 갱신
                    deserve = true;

                }
                else if ( giftRecordList[friendIndex][i] == giftRecordList[i][friendIndex]){
                    // 서로 주고 받은 선물 개수가 같거나 없는 경우 선물 지수 비교하기

                    if(giftQuotientMap.get(friend) > giftQuotientMap.get(targetFriend)){
                        // 내 선물 지수가 더 클 경우 경우 내가 받을 선물 개수 갱신
                        deserve = true;

                    }
                }

                if(deserve){
                    int giftCnt = giftPredictedMap.get( friend );
                    giftPredictedMap.replace( friend,giftCnt + 1 );
                }

            }
        }

        // 다음달에 받을 선물 개수 확인하기
        System.out.println("다음달에 받을 선물");
        for( Object o : giftPredictedMap.entrySet() ){
            System.out.print( o.toString() + " ");
        }
        System.out.println();

        // 최대값 리턴하기
        return Collections.max(giftPredictedMap.values());

    }
}

 

 

Main.java

public class Main {
    public static void main(String[] args) {

        Solution solution = new Solution();

        String[] friends = {"joy", "brad", "alessandro", "conan", "david"};
        String[] gifts = {"alessandro brad", "alessandro joy", "alessandro conan", "david alessandro", "alessandro david"};

        int answer = solution.solution(friends,gifts);
        System.out.println(answer);

    }
}

 

🖥️ 출력

선물 리스트(giftRecordList)
0 0 0 0 0 
0 0 0 0 0 
1 1 0 1 1 
0 0 0 0 0 
0 0 1 0 0 

선물 지수(giftQuotientMap)
joy=-1 alessandro=3 conan=-1 david=0 brad=-1 

다음달에 받을 선물(giftPredictedMap)
joy=0 alessandro=4 conan=0 david=3 brad=0

 

 

🔑 제출용 풀이

import java.util.*;


class Solution {
    static int[][] giftRecordList;                 // 받은 선물 개수 나타내는 다차원 배열

    static Map<String,Integer> giftQuotientMap;    // 각 사용자의 선물 지수

    static Map<String,Integer> giftPredictedMap;   // 각 사용자가 다음 달에 받을 선물 개수


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

        List<String> friendsList = Arrays.asList(friends);

        // 선물 기록 리스트 초기화
        giftRecordList = new int[friends.length][friends.length];

        // 선물 지수 맵 초기화
        giftQuotientMap = new HashMap<>();
        for( String friend : friends ) giftQuotientMap.put(friend, 0);

        // 다음 달에 받을 선물 개수 맵 초기화
        giftPredictedMap = new HashMap<>();
        for( String friend : friends ) giftPredictedMap.put( friend, 0 );


        for( String gift : gifts ){

            // [1] 문자열 띄어쓰기 기준으로 나누기
            String[] result = gift.split(" ");


            // [2] 선물 지수 값 갱신하기
            int giver = giftQuotientMap.get( result[0] );        // 선물 준 사람은 +1
            giftQuotientMap.replace( result[0], giver + 1 );

            int receiver = giftQuotientMap.get( result[1] );     //  선물 받은 사람은 -1
            giftQuotientMap.replace( result[1], receiver - 1 );


            // [3]  선물 받은 개수 리스트 값 갱신하기
            int giverIndex = friendsList.indexOf(result[0]);
            int receiverIndex = friendsList.indexOf(result[1]);
            giftRecordList[giverIndex][receiverIndex] += 1 ;

        }


        // 다음 달에 받을 선물 개수 계산하기
        for( String friend : friends ){
            for( int i = 0; i < friends.length; i++ ){

                int friendIndex = friendsList.indexOf(friend);
                String targetFriend = friendsList.get(i);       // 비교 대상인 상대방
                boolean deserve = false;

                if(friendIndex == i) continue;      // 본인 제외
                else if(giftRecordList[friendIndex][i] > giftRecordList[i][friendIndex]){
                    // 내가 준 선물 개수가 더 많을 경우 내가 받을 선물 개수 갱신
                    deserve = true;

                }
                else if ( giftRecordList[friendIndex][i] == giftRecordList[i][friendIndex]){
                    // 서로 주고 받은 선물 개수가 같거나 없는 경우 선물 지수 비교하기

                    if(giftQuotientMap.get(friend) > giftQuotientMap.get(targetFriend)){
                        // 내 선물 지수가 더 클 경우 경우 내가 받을 선물 개수 갱신
                        deserve = true;

                    }
                }

                if(deserve){
                    int giftCnt = giftPredictedMap.get( friend );
                    giftPredictedMap.replace( friend,giftCnt + 1 );
                }

            }
        }

        // 최대값 리턴하기
        return Collections.max(giftPredictedMap.values());

    }
}

 

 

완료!