[Coding Test] 프로그래머스 Lv1. 가장 많이 받은 선물

 

 

프로그래머스 Lv1 중 서치 없이 푸는데 실패한 문제를 정리한 내용입니다.

정리 내용 출처는 아래를 참고해 주세요.

 

---

 

문제 설명

 

친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 한다.

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

- 두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받는다.

- 선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값이다.

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

 

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

 

 

 

제한사항

• 2 <= friends의 길이 = 친구들의 수 <= 50
• friends의 원소는 친구의 이름을 의미하는 알파벳 소문자로 이루어진 길이가 10 이하인 문자열이다.
• 이름이 같은 친구는 없다.
• 1 <= gifts의 길이 <= 10,000
• gifts의 원소는 "A B" 형태의 문자열이다. A는 선물을 준 친구의 이름을, B는 선물을 받은 친구의 이름을 의미하며 공백 하나로 구분한다.
• A와 B는 friends의 원소이며 A와 B가 같은 이름인 경우는 존재하지 않는다.

 

입출력 예

 

friends	gift	result
["muzi", "ryan", "frodo", "neo"]	["muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muz"]	2
["joy", "brad", "alessandro", "conan", "david"]	["alessandro brad", "alessandro joy", "alessandro conan", "david alessandro", "alessandro david"]	4
["a", "b", "c"]	["a b", "b a", "c a", "a c", "a c", "c a"]	0

 

 

 

방식1 해설

 

frdIndex - 각 이름별로 인덱스 부여하기 위한 HashMap

1차원 배열 giftScore - 선물 지수

2차원 배열 giftGraph - 선물 주고 받은 횟수 각각

 

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int answer = 0;
        
        int frdLength = friends.length;
        
        HashMap<String, Integer> frdIndex = new HashMap<>();
        int[] giftScore = new int[frdLength];
        int[][] giftGraph = new int[frdLength][frdLength];
        
        for (int i = 0; i < frdLength; i++) {
            frdIndex.put(friends[i], i);
        }
        
        for (String gift : gifts) {
            String[] giftName = gift.split(" ");
            
            giftScore[frdIndex.get(giftName[0])]++;
            giftScore[frdIndex.get(giftName[1])]--;
            
            giftGraph[frdIndex.get(giftName[0])][frdIndex.get(giftName[1])]++;
        }
        
        for (int i = 0; i < frdLength; i++) {
            int num = 0;
            
            for (int j = 0; j < frdLength; j++) {
                if (giftGraph[i][j] == giftGraph[j][i] && giftScore[i] > giftScore[j]) {
                    num++;
                } else if (giftGraph[i][j] > giftGraph[j][i]) {
                    num++;
                }
            }
            
            if (answer < num) {
                answer = num;
            }
        }

        return answer;
    }
}

 

 

 

---