[Java] 2024 카카오 겨울 인턴십 코딩테스트 - 가장 많이 받은 선물

문제

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

풀이방향

시도한 코드

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int n = friends.length;
        int[] cal = new int[n];
        int[] counts = new int[n];
        
        //선물지수 계산
        for(int i=0;i<n;i++){
            int a = 0;
            int b = 0;
            for(String gift : gifts){
                if(gift.startsWith(friends[i])) a++;
                if((!gift.startsWith(friends[i])) && gift.contains(friends[i])) b++;
            }
            cal[i]=a-b;
        }
        

        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                int a=0;
                int b=0;
                for(String gift:gifts){
                    if(gift.contains(friends[i])&& gift.contains(friends[j])){
                        //friends[i]가 friens[j]에게 선물을 준 경우
                        if(gift.startsWith(friends[i])) a++;
                        else b++;
                    }
                }
                //다음달에 b가 하나 받는 경우
                if(a<b) counts[j]++;
                //다음달에 a가 하나 받는 경우
                else if(a>b) counts[i]++;
                //주고받은 수가 같아서 선물지수가 큰 사람이 받음
                else{
                    if(cal[i]>cal[j]) counts[i]++;
                    if(cal[i]<cal[j]) counts[j]++;
                }
            }
        }
        
        Arrays.sort(counts);
        return counts[n-1];
    }
}

• 우선 선물지수를 다 계산해서 저장해두는 게 편할 것 같았다.
• 선물지수를 계산해둘 배열 cal과, 받을 선물을 저장할 counts로 기록한 뒤, 마지막에 counts를 정렬해서 가장 큰 값을 return했다.

테스트 케이스에서는 통과했으나 제출했더니 절반정도가 틀렸다.
그 이유는 contains를 남발했기 때문인 것 같았다.

• 사실 띄어쓰기 단위로 준 사람과 받은 사람을 구분하는 방법이 있는건 아는데 어떤 메소드인지 기억이 안나서 그냥 contains()와 startsWith()를 버무려서 짰다. (와중에 또 endsWith()라는게 있는줄은 생각도 못해서 돌고 돌아감)
• 아니면 아예 공백을 포함해서 startsWith(friends[i] + " ")처럼 표현해도 가능하다.
• 이를 반영하면 코드에서 가장 더러웠던

if(gift.contains(friends[i])&& gift.contains(friends[j])){
    //friends[i]가 friens[j]에게 선물을 준 경우
    if(gift.startsWith(friends[i])) a++;
    else b++;
}

부분은

String[] parts = gift.split(" ");
if (parts[0].equals(friends[i]) && parts[1].equals(friends[j])) a++;
if (parts[0].equals(friends[j]) && parts[1].equals(friends[i])) b++;

이렇게 표현할 수 있다.
그리고 테스트도 바로 다 통과했다.

정리한 코드

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int n = friends.length;
        int[] cal = new int[n];
        int[] counts = new int[n];
        
        //선물지수 계산
        for(int i=0;i<n;i++){
            int a = 0;
            int b = 0;
            for(String gift : gifts){
                if(gift.startsWith(friends[i]+" ")) a++;
                if(gift.endsWith(" "+friends[i])) b++;
            }
            cal[i]=a-b;
        }
        
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                int a=0;
                int b=0;
                for(String gift:gifts){
                    String[] parts = gift.split(" ");
                    if (parts[0].equals(friends[i]) && parts[1].equals(friends[j])) a++;
                    if (parts[0].equals(friends[j]) && parts[1].equals(friends[i])) b++;
                }
                //다음달에 b가 하나 받는 경우
                if(a<b) counts[j]++;
                //다음달에 a가 하나 받는 경우
                else if(a>b) counts[i]++;
                //주고받은 수가 같아서 선물지수가 큰 사람이 받음
                else{
                    if(cal[i]>cal[j]) counts[i]++;
                    if(cal[i]<cal[j]) counts[j]++;
                }
            }
        }
        
        Arrays.sort(counts);
        return counts[n-1];
    }
}

---

https://tech.kakao.com/posts/610
☝️카카오에서 올려준 해설을 보면

해시맵을 이용해서 짜보면

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int n = friends.length;

        // 이름 -> 인덱스 매핑
        Map<String, Integer> idxMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            idxMap.put(friends[i], i);
        }

        // 선물 주고 받은 횟수 기록
        int[][] giftCount = new int[n][n];
        for (String gift : gifts) {
            String[] parts = gift.split(" ");
            int from = idxMap.get(parts[0]);
            int to = idxMap.get(parts[1]);
            giftCount[from][to]++;
        }

        // 선물 지수 계산 (준 선물 수 - 받은 선물 수)
        int[] giftPoint = new int[n];
        for (int i = 0; i < n; i++) {
            int given = 0, received = 0;
            for (int j = 0; j < n; j++) {
                given += giftCount[i][j];
                received += giftCount[j][i];
            }
            giftPoint[i] = given - received;
        }

        // 다음 달 받을 선물 수 계산
        int[] nextMonthGifts = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;

                if (giftCount[i][j] > giftCount[j][i]) {
                    nextMonthGifts[i]++;
                } else if (giftCount[i][j] == giftCount[j][i]) {
                    if (giftPoint[i] > giftPoint[j]) {
                        nextMonthGifts[i]++;
                    }
                }
            }
        }

        // 최댓값 반환
        return Arrays.stream(nextMonthGifts).max().getAsInt();
    }
}

반성하기

• String[] parts = gift.split(" ");
• startsWith()랑 contains()는 그래도 용케 생각해냄;;
• 무지, 라이언, 프로도, 네오 나오는 예시로만 생각하다가 친구들의 이름사이에 포함관계가 생길 수 있다는 건 진짜 꿈에도 생각 못했다..
• 해시맵은 아직 자유자재로 써먹기엔 실력이 부족한가보다