[프로그래머스] 가장 많이 받은 선물 - 구현(Implementation) + 2차원배열(two dimension array) + 해쉬맵(HashMap) JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/258712?language=java#

프로그래머스

코드설명

구현(Implementation) + 2차원배열(two dimension array) + 해쉬맵(HashMap) 를 활용하는 문제입니다.

 

문제는,  구현문제에서 2차원 배열과 해쉬맵을 사용하라는 의미로 카테고리를 이와 같이 나눴습니다. 

문제에서 가장 중요한점은, 문제를 읽고서 생각나는대로 바로 풀기보다는 문제 예시로 주어지는 형태를 만들고서 진행해야 디버깅이 쉽고, 오류없이 처리할 수 있을 것 같습니다.

 

아래의 코드는, 문제에서 주어진 예시를 그대로 구현합니다.

1. giftMap[][] :
   • giftMap은 각 친구 간에 주고 받은 선물의 수를 기록하는 2차원 배열입니다. giftMap[친구A][친구B]에는 A가 B에게 준 선물의 개수가 저장되어 있습니다.
   • gifts 배열을 순회하며 각 선물에 대한 정보를 받아와서 friendIndexHashMap을 이용하여 해당 친구들의 인덱스를 찾고, 이를 이용하여 giftMap을 채워나갑니다.
2. presentLevelMap[][] :
   • presentLevelMap은 각 친구의 준 선물, 받은 선물, 선물 지수를 저장하는 2차원 배열입니다. presentLevelMap[친구][0]은 해당 친구가 준 선물의 수, presentLevelMap[친구][1]은 받은 선물의 수, presentLevelMap[친구][2]는 선물 지수를 나타냅니다.
   • giftMap을 기반으로 각 친구에 대한 준 선물, 받은 선물의 수를 누적하고, 이를 바탕으로 선물 지수를 계산합니다.
3. friendIndexHashMap :
   • friendIndexHashMap은 각 친구의 이름을 인덱스로 매핑하는 해시맵입니다. HashMap<String, Integer> 형태로 구성되어 있습니다. 이를 통해 친구의 이름을 이용하여 해당 친구의 배열 인덱스를 빠르게 찾을 수 있습니다.
4. 다음 달 선물 계산:
   • nextMonthPresent 배열을 초기화하고, 주어진 규칙에 따라 다음 달에 각 친구가 얼마나 선물을 받을지를 계산합니다.
   • 두 친구 간에 주고 받은 기록이 있으면 그에 따라 처리하고, 주고 받은 기록이 없거나 서로 주고 받은 선물의 수가 같으면 선물 지수를 비교하여 결정합니다.
5. 최대 선물 개수 구하기:
   • 마지막으로 nextMonthPresent 배열을 순회하면서 각 친구가 받을 선물의 수를 확인하고, 그 중 가장 큰 값을 answer에 저장합니다.

제가 구현중에 실수했던 부분은, 다음달에 선물을 어떻게 줄지 정하는 부분에서 정확히 이해하지 못해 재차 확인했습니다.

문제 중에

두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.

이 부분을 두 사람 모두 서로에게 주어야하는 것이 아닌 한명이라도 다른사람에게 선물을 주었다면 그것은 서로 주고받은것이라고 판단합니다.

관련 코드입니다.

if( (presentAtoB > 0 || presentBtoA > 0) && presentAtoB != presentBtoA ){
...
...

코드

import java.util.*;
 
class Solution {
    
    /*
1. giftMap[freinds size][friends size] 을 생성한다.
2. gifts를 돌면서 giftMap[][] 을 채워나간다. 
2-1. 여기서 궁금한 점은, gifts를 돌면서 어떻게 사람이름을 매칭할 것 인가??
friends를 돌면서 직접 index를 찾아도 되지만, HASHMAP<FirendsName, Index> 에 넣어서 값을 넣어서 값을 찾는다.
3. presentLevelMap[friendSize][3] 를 선언한다.
    */
    public String[] Friends, Gifts;
    public int[][] giftMap;
    public int[][] presentLevelMap;
    public int[] nextMonthPresent;
    public int answer = 0;
    public int friendsSize = 0, giftsSize = 0;
    public HashMap<String, Integer> friendIndexHashMap = new HashMap<String, Integer>();
    public int solution(String[] friends, String[] gifts) {
        Friends = friends; Gifts = gifts;
        friendsSize = friends.length; giftsSize = gifts.length;
        giftMap = new int[friendsSize][friendsSize];
        nextMonthPresent = new int[friendsSize];
        presentLevelMap = new int[friendsSize][3];
        //해당 친구들의 인덱스를 friendIndexHashMap에 저장을 먼저 하겠습니다.
        for(int i=0;i<friendsSize; i++){
            friendIndexHashMap.put(Friends[i], i);
        }
        
        //이제 giftMap 2차원 배열을 gifts를 통해서 채워넣겠1]다.
        for(int i=0;i<giftsSize; i++){
            int givePeopleIndex = friendIndexHashMap.get(gifts[i].split(" ")[0]);
            int givenPeopleIndex = friendIndexHashMap.get(gifts[i].split(" ")[1]);
            
            //한개씩 증가시킵니다.
            giftMap[givePeopleIndex][givenPeopleIndex] += 1;
        }
        
        //이제 선물지수 presentLevelMap을 완성시킵니다.
        //준 선물, 받은선물, 선물 지수를 차례대로 넣습니다.
        //giftMap에서 각 row를 기준으로 col을 다 돕니다. 그리고 채워넣습니다.
        //어처피 사람이름을 구하는 것이 아닌, 최대로 많이 선물받은 선물의 개수를 구하면되기에
        //Index로 처리해도 됩니다.
        for(int row=0; row<friendsSize;row++){
            for(int col=0;col<friendsSize;col++){
                if(row == col){
                    continue;
                }
                
                //giftMap에 한개씩 더해줍니다.
                
                //준 선물을 채워줍니다.
                presentLevelMap[row][0] += giftMap[row][col];
                
                //받은 선물을 채워줍니다.
                presentLevelMap[col][1] += giftMap[row][col];
            }
        }
        
        //선물지수를 갱신합니다.
        for(int row = 0; row < friendsSize; row++){
            presentLevelMap[row][2] = presentLevelMap[row][0] - presentLevelMap[row][1];
        }
        
        //선물지수를 기반으로 다음달에 가장 선물을 많이 받을 사람을 구합니다.
        //이떄 첫번쨰 사람은 (두번쨰 사람과 세번쨰 사람과 네번쨰사람)
        //두번쨰 사람은 (세번쨰 사람과 네번쨰 사람)
        //세번쨰 사람은 (네번쨰 사람)
        //네번쨰 사람은 없음.
        
        //위와 같이 진행됩니다.
        
        //규칙이 존재합니다.
        
        
        for(int row=0; row< friendsSize; row++){
            for(int col=row+1; col < friendsSize; col++){
                //A가 B에게 준 선물
                int presentAtoB = giftMap[row][col];     
                //B가 A에게 준 선물
                int presentBtoA = giftMap[col][row];
                
                //두 사람이 선물을 주고받은 기록이 있다면, 
                //선물을 주고받은 기록이 더 많은지 적은지 모르겠지만, 문제에서 나온 순서대로 진행한다.(최대한 적은 수가 if문 앞에 나오도록 하는것이 좋다.)
                System.out.println("ryan-frodo is not working now"+presentAtoB+" "+presentBtoA);
            
                //내가 놓쳣었던점은, presentAtoB, BtoA가 한개라도 0 보다 크다면 서로 주고받은것이고, 그 주고받은 상황에서 서로 같은 선물의 양을 주고받지 않도록 처리해야합니다.
                //처음에는 단순하게 두개다 무조건 0 보다 큰경우, 즉 무조건 서로에게 한개씩 이상 준경우로 연산하였습니다.
                //문제를 보면 선물을 주고받은 기록이란 서로에게 한개라도 준경우를 말합니다. (어떤 사람이 안주었다고해도 서로 주고받은경우로 처리합니다.)
                //두 사람이 선물을 주고받았으면서, 주고받은수가 같지 않다면
                if( (presentAtoB > 0 || presentBtoA > 0) && presentAtoB != presentBtoA ){
                    
                    //만약 A가 더 많이 주었다면, A가 다음번에 선물을 받을 것 이다.
                    if(presentAtoB > presentBtoA){
                        nextMonthPresent[row] += 1;
                    } 
                    //만약 B가 더 많이 줬다면 다음달에 B가 받는다.
                    else if(presentAtoB < presentBtoA){
                        nextMonthPresent[col] += 1;
                    }
                }
                
                //두 사람이 선물을 주고받은 기록이 없거나, 서로 주고받은수가 같다면
                else if( (presentAtoB == 0 && presentBtoA == 0) || (presentAtoB == presentBtoA) ){
                    //선물지수가 더 큰 사람이 선물지수가 더 작은 사람에게 선물을 하나 받는다.
                    int AGiftLevel = presentLevelMap[row][2];
                    int BGiftLevel = presentLevelMap[col][2];
                    
                    //A의 선물지수가 더 크다면, A 가 받는다.
                    if(AGiftLevel > BGiftLevel){
                        nextMonthPresent[row] += 1;
                    } else if(AGiftLevel < BGiftLevel){
                        nextMonthPresent[col] += 1;
                    } else if(AGiftLevel == BGiftLevel){
                        
                    }
                }
                
                
            
                
            }
        }
        
        for(int i=0; i<friendsSize;i++){
            for(int j=0;j<friendsSize; j++){
                System.out.print(" "+giftMap[i][j]);
            }
            System.out.println();
        }
         System.out.println();
        for(int i=0; i<friendsSize;i++){
            for(int j=0;j<3; j++){
                System.out.print(" "+presentLevelMap[i][j]);
            }
            System.out.println();
        }
        
        System.out.println();
        for(int i=0;i<friendsSize;i++){
            System.out.print(" "+nextMonthPresent[i]);
            answer = Math.max(answer, nextMonthPresent[i]);
        }
        
        return answer;
    }
}

 

정답코드2입니다.

이 경우, 항상 선물을 주고받을떄 항상 from의 입장에서만 검사합니다.

import java.util.*; 
 
class Solution {
    String[] Friends;
    String[] Gifts;
    HashMap<String, Integer> Hashmap = new HashMap<>();
    int answer = 0;
    public int solution(String[] friends, String[] gifts) {
        Friends = friends;
        Gifts = gifts;
        
        for(int i=0; i<Friends.length; i++){
            Hashmap.put(Friends[i], i);
        }
        
        int[][] Matrix = new int[Friends.length][Friends.length];
        int[][] Status = new int[Friends.length][3];
        for(int i=0; i<Gifts.length; i++){
            String[] splitWord = Gifts[i].split(" ");
            int from = toNumber(splitWord[0]);
            int to = toNumber(splitWord[1]);
            
            Matrix[from][to] += 1;
            Status[from][0] += 1;
            Status[from][2] += 1;
            Status[to][1] += 1;
            Status[to][2] -= 1;
        }
        
        int[] answer = new int[Friends.length];
        
        for(int i=0; i<Friends.length; i++){
            for(int j=0; j<Friends.length; j++){
                if(i!=j){
                    int from = i; int to = j;    
                    //두 사람이 선물을 주고받은 기록이 있다면, //이번달까지 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.
                    if( (Matrix[from][to] > 0) && (Matrix[from][to] > Matrix[to][from]) ){
                        if(i==1) System.out.print("correct");
                        answer[from] += 1;
                    }
                    //두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, //선물지수가 더 큰사람이 선물지수가 더 작은사람에게 선물을 하나 받습니다.
                    else if( (Matrix[from][to] == 0 && Matrix[to][from] == 0) || (Matrix[from][to] == Matrix[to][from]) ){
                        int fromStatus = Status[from][2];
                        int toStatus = Status[to][2];
                        if(fromStatus > toStatus){
                            answer[from] += 1;
                        }
                    }
                }                
            }
        }
        int MAXANSWER = 0;
        for(int i=0; i<answer.length; i++){
            MAXANSWER = Math.max(MAXANSWER, answer[i]);
        }
        
        return MAXANSWER;
    }
    
    public int toNumber(String name){
        return Hashmap.get(name);
    }
}