[프로그래머스] Lv.1 추억 점수 (Java)

프로그래머스

 

===문제 설명===

사진별로 추억 점수를 매기려고 합니다.

사진 속에 나오는 인물의 그리움 점수를 모두 합산한 값이 해당 사진의 추억 점수가 됩니다.

이름	may	kein	kain
추억 점수	5	10	1

사진 속 사람의 추억 점수가 없다면 -> [0점]

 

 

그리워하는 사람의 이름을 담은 문자열 배열 name,  각 사람별 그리움 점수를 담은 정수 배열 yearning, 각 사진에 찍힌 인물의 이름을 담은 이차원 문자열 배열 photo 가 매개변수로 주어집니다.

사진들의 추억 점수를   photo에 주어진 순서대로 배열에 담아 return 하는 solution함수를 완성해 주세요.

 

---

 🌟 T I P 🌟  : 배열을 사용하지 않는 이유.!

may	kein	kain
5	10	1

배열로 사람별 추억점수를 찾는다면, 배열을 처음부터 끝까지 돌면서 사진 속 인물과 같은 사람을 찾고, 그 사람의 추억 점수를 가져옵니다.

이 경우 사진 속 사람이 추억점수가 없다면 최악의 경우 계속 추억점수 배열을 매번 끝까지 찾을 수도 있습니다.

이 방법은 시간복잡도가 O(n)으로 효율성이 떨어집니다.

 

배열 말고 해시를 사용한다면?!

 

해시는 해시함수가 알아서 키에 해당하는 해시값을 매핑해 주고, 그 해시값에 저장된 value값을 가져와주기 때문에

연산 속도가 훨씬 빨라집니다.

이 방법은 시간복잡도가 O(1)로 가장 빠릅니다.

 

 

 

🔖  풀이과정  

1. <key=인물, value=추억점수>를 담을 HashMap을 만들어주고, 그 안에 주어진 name, yearning 값을 넣어줍니다.

HashMap<String,Integer> score = new HashMap<>();//인물-추억점수

for(int i=0;i<name.length;i++) score.put(name[i],yearning[i]);

 

 

2. 사진을 하나씩 가져와서 그 사진의 추억점수의 합을 저장할 변수를 만들어 줍니다.

for(int i=0;i<photo.length;i++){
    int s=0;//i번째 사진의 추억점수의 합

 

 

3. i번째 사진의 인물을 한 명씩 보고 HashMap에서 해당 인물이 있는지 확인하고, 있다면 그 인물의 추억점수를 가져와 해당 사진의 추억점수 합에 저장해 줍니다.

for(int j=0;j<photo[i].length;j++){
	//i번째 사진 -> j번째 인물이 추억점수를 가지는지 확인
    if(score.containsKey(photo[i][j]))
        s+=score.get(photo[i][j]); //현재 인물이 추억점수를 가진다면, 그 점수를 s에 저장.
}

 

<---더 좋은 방법--->

Map의 getOrDefault라는 메서드를 사용하면 훨씬 간편하고 간결해집니다.

map.getOrDefault(key,0);

//map에 key가 있다면 -> 그 key의 value 값 반환
//      key가 없다면 -> default값인 0 반환 (default값은 내가 설정할 수 있습니다!)

 

score에 photo [i][j]가 있다면 -> 그 value값을 반환,     없다면 -> default값=0 반환! 

s+=score.getOrDefault(photo[i][j],0);

 

 

4. i 번째 사진의 추억점수의 합을 answer배열에 넣어주고, photo를 모두 조사하였으면 answer 배열을 반환해 줍니다.

    answer[i]=s; // i번째 사진의 추억점수의 합을 answer에 넣기
    }
    
return answer;

---

전체 코드

import java.util.*;
class Solution {
    public int[] solution(String[] name, int[] yearning, String[][] photo) {
        int[] answer = new int[photo.length];
        
        HashMap<String,Integer> score = new HashMap<>();//인물-추억점수
        for(int i=0;i<name.length;i++) score.put(name[i],yearning[i]);
        
        for(int i=0;i<photo.length;i++){
            int s=0;//i번째 사진의 총 추억점수
            for(int j=0;j<photo[i].length;j++){
                //i번째 사진 -> j번째 인물이 추억점수를 가지는지 확인.
                if(score.containsKey(photo[i][j])) //O(1)
                    s+=score.get(photo[i][j]); //O(1)
            }
            answer[i]=s;//i번째 사진의 총 추억점수 answer에 넣기.
        }
        return answer;
    }
}

시간복잡도: O(n)
공간복잡도: O(n)