[세모] 프로그래머스 가장많이 받은 선물 // 구현, 해시맵, 문자열을 인덱스로

* 풀이1

일단 문제를 읽으며 도식화를 진행.

문제의 예시에서 힌트를 얻어, 그래프형태로 만들기

graph[i][j] : i가 j에게 준 선물 수

문제1 : string을 배열의 인덱스로 쓰려면?

map을 이용해 매핑

문제2 : 둘다 주고받지않는것을 어떻게 판단?

graph[i][j], [j][i]가 둘다 0인경우

처음 제출 코드 (답이 2배가 되는 문제)

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int answer = 0;
        int n = friends.length;
        
        HashMap<String, Integer> m1 = new HashMap<>(); //str to index
        HashMap<Integer, String> m2 = new HashMap<>(); //index to str
        
        HashMap<String, Integer> m4 = new HashMap<>(); //선물지수
        HashMap<String, Integer> ret = new HashMap<>(); //받을선물수
        
        for(int i=0;i<n;++i){
            m1.put(friends[i],i);
            m2.put(i,friends[i]);
            m4.put(friends[i],0);
            ret.put(friends[i],0);
        }
        // System.out.println(m1);
        
        int graph[][] = new int[n][n];
        for(int i=0;i<gifts.length;++i){
            String[] tmp = gifts[i].split(" ");
            String from = tmp[0];
            String to = tmp[1];
            graph[m1.get(from)][m1.get(to)] +=1;
            
            m4.put(from,m4.get(from)+1);
            m4.put(to,m4.get(to)-1);
            
//             if(m2.containsKey(from)){
//                 m2.put(from,m2.get(from)+1);
//             }
//             else{
//                 m2.put(from,1);
//             }
            
//             if(m3.containsKey(to)){
//                 m3.put(from,m3.get(to)+1);
//             }
//             else{
//                 m3.put(from,1);
//             }
            
        }
        // for(int i=0;i<n;++i){
        //     for(int j=0;j<n;++j){
        //         System.out.print(graph[i][j]+" ");
        //     }System.out.println();
        // }
        
        // System.out.println(m4);
        
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                //주고받지않은경우
                if(graph[i][j]==0 && graph[j][i]==0){
                    if(m4.get(m2.get(i)) > m4.get(m2.get(j))){
                        ret.put(m2.get(i),ret.get(m2.get(i))+1); //i가 받을선물 + 1
                    }
                    else if(m4.get(m2.get(i)) < m4.get(m2.get(j))){
                        ret.put(m2.get(j),ret.get(m2.get(j))+1); //j가 받을선물 + 1
                    }
                }
                else {
                    if(graph[i][j] > graph[j][i]){
                        ret.put(m2.get(i),ret.get(m2.get(i))+1); //i가 받을선물 + 1
                    }
                    else if(graph[i][j] < graph[j][i]){
                        ret.put(m2.get(j),ret.get(m2.get(j))+1); //j가 받을선물 + 1
                    }
                    else{ //선물지수도 같다면
                        if(m4.get(m2.get(i)) > m4.get(m2.get(j))){
                            ret.put(m2.get(i),ret.get(m2.get(i))+1); //i가 받을선물 + 1
                        }
                        else if(m4.get(m2.get(i)) < m4.get(m2.get(j))){
                            ret.put(m2.get(j),ret.get(m2.get(j))+1); //j가 받을선물 + 1
                        }
                    }
                }
            }
        }
        
        answer=0;
        
        System.out.println(ret);
        
        for(String key : ret.keySet()){
            if(ret.get(key) > answer){
                answer=ret.get(key);
            }
        }
        
        return answer/2;
    }
}

 

 

문제3 : 처음코드에서 답이 2배가 된 이유?

i,j로 순회하면서 j가 큰경우, j도 갱신해주었기 때문

ex) muzi에서 ryan이 더커서 ryan을 +1

ryan 에서 내가더크니까 ryan을 +1 //중복!

 

해결방법

1. 정답을 2로 나누기 (직관적)

2. j를 i+1부터 순회하기.

ex) ryan은 muzi를 제외하고 탐색. frodo는 neo부터 탐색 ...

3. 단순히 j갱신 로직을 제거하기 -> 안됨.

4. 각 i중심으로 생각하기

//record == graph
//index[i] : i의 선물지수

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;

 

정답코드

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int answer = 0;
        int n = friends.length;
        
        HashMap<String, Integer> m1 = new HashMap<>(); //str to index
        HashMap<Integer, String> m2 = new HashMap<>(); //index to str
        
        HashMap<String, Integer> m4 = new HashMap<>(); //선물지수
        HashMap<String, Integer> ret = new HashMap<>(); //받을선물수
        
        for(int i=0;i<n;++i){
            m1.put(friends[i],i);
            m2.put(i,friends[i]);
            m4.put(friends[i],0);
            ret.put(friends[i],0);
        }
        // System.out.println(m1);
        
        int graph[][] = new int[n][n];
        for(int i=0;i<gifts.length;++i){
            String[] tmp = gifts[i].split(" ");
            String from = tmp[0];
            String to = tmp[1];
            graph[m1.get(from)][m1.get(to)] +=1;
            
            m4.put(from,m4.get(from)+1);
            m4.put(to,m4.get(to)-1);
            
        }
        // for(int i=0;i<n;++i){
        //     for(int j=0;j<n;++j){
        //         System.out.print(graph[i][j]+" ");
        //     }System.out.println();
        // }
        
        // System.out.println(m4);
        
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(i==j) continue;
                
                //주고받지않은경우
                if(graph[i][j]==0 && graph[j][i]==0){
                    if(m4.get(m2.get(i)) > m4.get(m2.get(j))){
                        ret.put(m2.get(i),ret.get(m2.get(i))+1); //i가 받을선물 + 1
                    }
                    else if(m4.get(m2.get(i)) < m4.get(m2.get(j))){
                        ret.put(m2.get(j),ret.get(m2.get(j))+1); //j가 받을선물 + 1
                    }
                }
                else {
                    if(graph[i][j] > graph[j][i]){
                        ret.put(m2.get(i),ret.get(m2.get(i))+1); //i가 받을선물 + 1
                    }
                    else if(graph[i][j] < graph[j][i]){
                        ret.put(m2.get(j),ret.get(m2.get(j))+1); //j가 받을선물 + 1
                    }
                    else{ //주고받은게 같으면, 선물지수
                        if(m4.get(m2.get(i)) > m4.get(m2.get(j))){
                            ret.put(m2.get(i),ret.get(m2.get(i))+1); //i가 받을선물 + 1
                        }
                        else if(m4.get(m2.get(i)) < m4.get(m2.get(j))){
                            ret.put(m2.get(j),ret.get(m2.get(j))+1); //j가 받을선물 + 1
                        }
                    }
                }
            }
        }
        
        answer=0;
        
        System.out.println(ret);
        
        for(String key : ret.keySet()){
            if(ret.get(key) > answer){
                answer=ret.get(key);
            }
        }
        
        return answer;
    }
}