프로그래머스 Lv1 - 가장 많이 받은 선물

문제

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

프로그래머스

 

풀이시간 : 42분 1:06 ~ 1:48

시도 횟수 : 1

복기 : 오래간만에 프로그래머스에서 풀려고하니, 익숙치 않았다. 자료구조 선언하는데 Import 를 해야한다니..

 

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        
        Map<String, Integer> friendsMap = new HashMap<>();
        for(int i = 0 ; i < friends.length ; i++){
            friendsMap.put(friends[i], i);
        }
        
        int[][] giftMap = new int[51][51];
        int[] giftScore = new int[51];
        for(String gift : gifts){
            String[] target = gift.split(" ");
            int from = friendsMap.get(target[0]);
            int to = friendsMap.get(target[1]);
            
            giftMap[from][to] += 1;
            giftScore[from] += 1;
            giftScore[to] -= 1;
        }
        
        int[] receivedGift = new int[51];
        for(int i = 0 ; i < friends.length ; i++){
            for(int j = i + 1 ; j < friends.length ; j++){
                int from = giftMap[i][j]; // i가 j에게 준 선물 횟수
                int to = giftMap[j][i]; // j가 i에게 준 선물 횟수
                
                // 선물을 주고 받은 기록이 같은 경우
                if (from == to) {
                    if (giftScore[i] > giftScore[j]) {
                        receivedGift[i] += 1;
                    } else if(giftScore[i] < giftScore[j]) {
                        receivedGift[j] += 1;
                    }
                } else if (from > to) {
                    receivedGift[i] += 1;
                } else {
                    receivedGift[j] += 1;
                }
            }
        }
        
        int answer = 0;
        for(int score : receivedGift){
            if(answer < score){
                answer = score;
            }
        }
        
        return answer;
    }
}

 

더 나은 풀이 방법

기본적으로 나와 풀이방식은 같다.

다만 Max Scoring 하는 과정에서 로직을 좀 더 단순화 하였다.

감을 좀 더 높혀보자.

import java.util.*;

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

        for (String str : gifts) {
            String[] cur = str.split(" ");
            index[map.get(cur[0])]++;
            index[map.get(cur[1])]--;
            record[map.get(cur[0])][map.get(cur[1])]++;
        }

       int ans = 0;
       for (int i = 0; i < friends.length; i++) {
           int cnt = 0;
           for (int j = 0; j < friends.length; j++) {
               if(i == j) continue;
               if (record[i][j] > record[j][i]) cnt++;
               else if (record[i][j] == record[j][i] && index[i] > index[j]) cnt++; 
           }
           ans = Math.max(cnt, ans);
       }
        return ans;
    }
}