[Conc & Sol] `HashMap`이 아닌 배열 인덱스를 사용하여 간단하게 문제를 해결하는 방법

▼ Why ? What ?

1일 1알고리즘 스터디에서 "가장 많이 받은 선물"이라는 문제를 풀었는데, 요근래 풀었던 알고리즘 문제 중에 가장 시간이 오래 걸렸던 문제였던 것 같다. 문제가 그렇게 어렵지는 않았는데, HashMap을 여러 번 사용하다보니 코드가 복잡해져서 어떤 부분에서 NPE가 발생하는지를 찾는 데 시간이 오래 걸렸고, 복잡한 코드를 계속 보다보니 머리도 잘 안돌아갔던 것 같다.. 다른 사람의 해결 코드를 통해 HashMap에만 의존하지 않고 배열을 이용하여 더 간단하게 풀어낸 방식을 볼 수 있었다. 이 풀이 방식은 나중에 유용하게 활용해볼 수 있을 것 같아서, 해당 로직을 참고하여 코드를 다시 작성해봤다.

---

▼ 알고리즘 문제 : "가장 많이 받은 선물"

 

가장 많이 받은 선물

프로그래머스

 

[ 나의 해결 코드 1 ]

• HashMap를 전적으로 활용해서 저장한 데이터들을 일일히 꺼내와 값을 비교하고 문제에서 원하는 값을 추출해내는 방식으로 코드를 작성하였다.
  ➙ 이 방법도 틀리지 않았지만, HashMap의 제네릭 타입에 또 HashMap을 사용하다보니 코드가 복잡해져서 문제를 해결하는 데 시간이 오래 걸렸던 것 같다. ( 다음부터는 이런 로직은 최대한 피하고 이후에 나올 코드의 로직을 활용해보자 ! )

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int maxReceivedGifts = 0;
        HashMap<String, HashMap<String, Integer>> sendMap = new HashMap<>();
        HashMap<String, Integer> friendToPoint = new HashMap<>();
        
        for (String sender : friends) {
            sendMap.putIfAbsent(sender, new HashMap<String, Integer>());
            friendToPoint.put(sender, 0); // 모든 사람의 선물 지수를 0으로 세팅 -> 선물을 주지도 받지도 않은 사람을 따로 예외 처리해줄 필요 X
            for (String receiver : friends) {
                if (receiver.equals(sender)) continue;
                sendMap.get(sender).put(receiver, 0); // 선물을 주고받은 기록이 없더라도 0으로 초기화
            }
        }
        
        for (String gift : gifts) {
            String[] sr = gift.split(" ");
            String sender = sr[0];
            String receiver = sr[1];
            
            HashMap<String, Integer> recToCnt = sendMap.get(sender);
            recToCnt.put(receiver, recToCnt.get(receiver) + 1);
            
            friendToPoint.put(sender, friendToPoint.get(sender) + 1);
            friendToPoint.put(receiver, friendToPoint.get(receiver) - 1);
        }
        
        for (String sender : friends) {
            int nextGifts = 0;
            for (String receiver : friends) {
                if (receiver.equals(sender)) continue;
                
                int sendCnt1 = sendMap.get(sender).get(receiver); // sender -> receiver 선물 개수
                int sendCnt2 = sendMap.get(receiver).get(sender); // receiver -> sender 선물 개수
                int point1 = friendToPoint.get(sender); // sender의 선물 지수
                int point2 = friendToPoint.get(receiver); // receiver의 선물 지수
                
                if (sendCnt1 == sendCnt2) { // 주고받은 기록이 하나도 없거나 주고받은 수가 같은 경우
                    if (point1 > point2) { // sender의 선물 지수가 더 높은 경우
                        nextGifts++;
                    }
                } else if (sendCnt1 > sendCnt2) { // sender가 receiver에게 다음 달에 선물을 받아야 하는 경우
                    nextGifts++;
                }
            }
            
            maxReceivedGifts = Math.max(maxReceivedGifts, nextGifts);
        }
        
        return maxReceivedGifts;
    }
}

 

[ 나의 해결 코드 2 ]

• 배열을 활용하니 코드가 더 컴팩트해진 것을 확인해볼 수 있다.
  ➙ 2차원 배열을 활용한 로직을 기억해두면 좋을 것 같다.

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        Map<String, Integer> friendToIndex = new HashMap<>();
        for (int i = 0; i < friends.length; i++) {
            friendToIndex.put(friends[i], i);
        }
        int[] points = new int[friends.length];
        int[][] record = new int[friends.length][friends.length];

        for (String gift : gifts) {
            String[] rs = gift.split(" ");
            String sender = rs[0];
            String receiver = rs[1];
            points[friendToIndex.get(sender)]++;
            points[friendToIndex.get(receiver)]--;
            record[friendToIndex.get(sender)][friendToIndex.get(receiver)]++;
        }

       int maxGifts = 0;
       for (int i = 0; i < friends.length; i++) {
           int nextGifts = 0;
           for (int j = 0; j < friends.length; j++) {
               if(i == j) continue; // 본인인 경우
               if (record[i][j] > record[j][i]) { // sender가 receiver에게 다음 달에 선물을 받아야 하는 경우
                   nextGifts++; 
               } else if (record[i][j] == record[j][i] && points[i] > points[j]) { // 주고받은 개수가 같고 i의 선물 지수가 더 높은 경우
                   nextGifts++; 
               }
           }
           maxGifts = Math.max(nextGifts, maxGifts);
       }
        return maxGifts;
    }
}