[프로그래머스/JAVA] 가장 많이 받은 선물

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 💡 아이디어
• 👩🏻‍💻 최종 코드
• 🕑 시간 복잡도

 

 

 

🔗 문제 바로가기

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

프로그래머스

 

---

📌 문제 요약

 

친구들 간에 선물을 주고받은 기록을 바탕으로 다음 달에 가장 많은 선물을 받는 친구는 선물을 몇 개 받을지 찾아야 한다.

 

다음 달에는 아래의 세 가지 조건에 따라 선물을 받을 예정이다.

• A와 B가 주고받은 선물의 수가 다르면, 둘 사이에서 더 많이 선물했던 사람이 선물을 하나 받는다.
• A와 B가 주고받은 선물의 수가 같거나 기록이 없으면, 선물지수가 더 높은 사람이 선물을 하나 받는다.
  (선물 지수 = 내가 준 선물 수 - 내가 받은 선물 수)
• 주고받은 선물의 수도 같고, 선물지수도 같다면, 아무도 선물을 받지 않는다.

 

📥 입력

• friends
  • 친구들의 이름을 담은 문자열 배열
  • ex. ["muzi", "ryan", "frodo", "neo"]
  • 길이는 2 이상 50 이하
  • 각 이름은 중복 없이, 알파벳 소문자로 구성된 최대 10글자
• gifts
  • 선물을 주고받은 기록을 담은 문자열 배열
  • ex. ["muzi frodo", "ryan muzi"]
  • 각 원소는 "보낸사람 받은사람" 형태 (공백으로 보낸 사람과 받은 사람을 구분)
  • 길이는 1 이상 10,000 이하
  • 같은 사람이 자기 자신에게 선물하는 경우는 없음

 

---

💡 아이디어

1️⃣ 친구 쌍 간의 선물 기록 정리

int[][] cnt = new int[m][m];
int[] give_total = new int[m];
int[] receive_total = new int[m];

 

• cnt[i][j]: i번 친구가 j번 친구에게 준 선물의 수
• give_total[i]: i번 친구가 전체 친구들에게 준 선물 수
• receive_total[i]: i번 친구가 전체 친구들로부터 받은 선물 수

👉🏻 이 정보들을 이용해서 선물 관계와 선물 지수를 모두 계산할 수 있게 준비했다.

 

 

2️⃣ 선물 기록 파싱 및 누적

for(int i = 0; i < n; i++){
    String[] gift = gifts[i].split("\\s");
    String giver = gift[0];
    String receiver = gift[1];
            
    int row = 0, col = 0;
            
    for(int j = 0; j < m; j++){
        if(giver.equals(friends[j])){
            row = j;
            give_total[j]++;
        }
                
        if(receiver.equals(friends[j])){
            col = j;
            receive_total[j]++;
        }
    }
            
    cnt[row][col]++;
}

 

• gifts 배열을 순회하며, giver와 receiver의 인덱스를 friends에서 찾기
• 이에 따라 cnt와 give_total, receive_total을 모두 업데이트 해주기

 

3️⃣ 모든 친구 쌍에 대해 다음 달 받을 선물 계산

for(int i = 0; i < m; i++){
    for(int j = 0; j < m; j++){
    if(i == j){
            continue;
    }
                
     if(cnt[i][j] > cnt[j][i]){
            answer[i]++;
     }
     else if(cnt[i][j] < cnt[j][i]){
            answer[j]++;
     }   
     else{
            int tmp1 = give_total[i] - receive_total[i];
            int tmp2 = give_total[j] - receive_total[j];
                    
            if(tmp1 > tmp2){
                answer[i]++;
            }
            else if(tmp1 < tmp2){
                answer[j]++;
            }
        }
                
    }
}

 

• 각 친구쌍 (i, j)에 대해 선물을 주고받은 기록을 비교
• 자기 자신에게 선물을 할 수는 없으니 i == j라면 건너뛰기
• 주고 받은 선물 수가 다른 경우, 선물을 더 많이 한 친구가 다음 달에 선물을 하나 받음
• 주고받은 선물 수가 같으면, 선물지수를 비교해서 더 큰 쪽이 선물을 하나 받음
• 선물지수 마저 같다면 아무도 선물을 받지 않음

 

4️⃣ 가장 많은 선물을 받는 친구 찾기

int max = 0;
for(int i = 0; i < m; i++){
    if(answer[i] > max){
        max = answer[i];
    }
}

return max / 2;

 

• 최종적으로 가장 많이 받은 선물의 개수를 max에 저장
• 이 때 모든 (i, j) 쌍을 다 비교하면서 서로 주고받은 선물을 두 번씩 계산했기 때문에, 결과를 2로 나눠서 반환

 

---

👩🏻‍💻 최종 코드

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int n = gifts.length;
        int m = friends.length;
        
        int[][] cnt = new int[m][m];
        int[] give_total = new int[m];
        int[] receive_total = new int[m];
        int[] answer = new int[m];
        
        for(int i = 0; i < n; i++){
            String[] gift = gifts[i].split("\\s");
            String giver = gift[0];
            String receiver = gift[1];
            
            int row = 0, col = 0;
            
            for(int j = 0; j < m; j++){
                if(giver.equals(friends[j])){
                    row = j;
                    give_total[j]++;
                }
                
                if(receiver.equals(friends[j])){
                    col = j;
                    receive_total[j]++;
                }
            }
            
            cnt[row][col]++;
        }
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                if(i == j){
                    continue;
                }
                
                if(cnt[i][j] > cnt[j][i]){
                    answer[i]++;
                }
                else if(cnt[i][j] < cnt[j][i]){
                    answer[j]++;
                }   
                else{
                    int tmp1 = give_total[i] - receive_total[i];
                    int tmp2 = give_total[j] - receive_total[j];
                    
                    if(tmp1 > tmp2){
                        answer[i]++;
                    }
                    else if(tmp1 < tmp2){
                        answer[j]++;
                    }
                }
                
            }
        }
        
        int max = 0;
        for(int i = 0; i < m; i++){
            if(answer[i] > max){
                max = answer[i];
            }
        }
        
        return max / 2;
    }
}

 

---

🕑 시간 복잡도

1️⃣ 선물 기록 파싱 및 배열 누적

for (int i = 0; i < n; i++) {
    ...
    for (int j = 0; j < m; j++) {
        if (giver.equals(friends[j])) ...
        if (receiver.equals(friends[j])) ...
    }
}

 

• 바깥 루프는 n번
• 안쪽 루프는 m번

👉🏻 여기서의 시간 복잡도는 O(n * m)

 

2️⃣ 모든 친구 쌍에 대해 선물 비교

for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
        if (i == j) continue;
        ...
    }
}

 

• 모든 친구 쌍 (i != j) 비교

👉🏻 여기서의 시간 복잡도는 O(m²)

 

3️⃣ 최댓값 계산

for (int i = 0; i < m; i++) {
    ...
}

 

• 친구 수만큼 순회

👉🏻 여기서의 시간 복잡도는 O(m)

 

 

따라서 최종 시간 복잡도는 O(n * m + m²)이다.

(이때 n은 선물 기록 수, m은 친구 수)