[프로그래머스/JAVA] 추억 점수

목차 (OPEN)

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

 

 

 

🔗 문제 바로가기

 

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

프로그래머스

 

---

📌 문제 요약

 

 

🖼️ 추억 점수 계산하기

• 규칙
  • 사진 속 인물의 이름을 확인한다.
  • 해당 인물이 name[ ]에 있으면 → yearning[ ]에서 점수를 가져온다.
  • 점수를 모두 더한 값이 그 사진의 추억 점수이다.
  • 이를 모든 사진에 대해 반복해서 결과 배열을 반환해야 한다.

 

💌 입력

• name[ ] → 그리워하는 사람 이름 목록
• yearingp[ ]  → 각 사람의 그리움 점수
• photo[ ][ ] → 사진 속 인물들의 이름 목록

 

 

예를 들면 아래와 같다.

name:    ["may", "kein", "kain", "radi"]
yearning:[5,     10,     1,      3]
photo:   [
           ["may", "kein", "kain", "radi"],  // 5+10+1+3 = 19
           ["may", "kein", "brin", "deny"],  // 5+10 = 15
           ["kon", "kain", "may", "coni"]    // 1+5 = 6
         ]
결과: [19, 15, 6]

 

---

💡 아이디어

1️⃣이름 → 점수 매핑 생성

사진을 순회할 때 이름의 점수를 O(1)에 조회하기 위해

name[i]와 yearning[i]를 매칭하여 Map<String, Integer>에 저장해준다.

Map<String, Integer> map = new HashMap<>();
for(int i = 0; i < name.length; i++){
    map.put(name[i], yearning[i]);
}

 

 

2️⃣ 사진별 합계 계산하기

1. photo의 각 행(= 한 장의 사진)을 순회한다.
2. 이 과정에서 사진 속 인물 이름들을 하나씩 가져와서 맵에서 점수 조회 후 합산한다.
3. 만약 이름이 맵에 없다면, getOrDefault(person, 0)으로 0점 처리한다.
4. 계산된 합계를 answer[i]에 저장한다.

for(int i= 0; i < photo.length; i++){
    int sum = 0;
            
    for(int j = 0; j < photo[i].length; j++){
        String person = photo[i][j];
        sum += map.getOrDefault(person, 0);
    }
            
    answer[i] = sum;
}

 

 

나는 3번째 부분에서 시간을 잡아 먹었다 (ŏ̥̥̥̥ ɞŏ̥̥̥̥)

사진에 있는 인물이 맵에 없을 수도 있다는 점을 생각 못했기 때문이다 ..ㅎㅎ

왜 통과가 안 되는 거지 하며 한참을 고민했었는데,

이 글을 보는 분들은 문제를 꼼꼼히 읽고 풀기를 ,,ʚ₍⑅ᐢ‸ ̫ ‸ᐢ₎ɞ

 

---

👩🏻‍💻 최종 코드

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] solution(String[] name, int[] yearning, String[][] photo) {
        
        int[] answer = new int[photo.length];
        
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < name.length; i++){
            map.put(name[i], yearning[i]);
        }
        
        for(int i= 0; i < photo.length; i++){
            int sum = 0;
            
            for(int j = 0; j < photo[i].length; j++){
                String person = photo[i][j];
                sum += map.getOrDefault(person, 0);
            }
            
            answer[i] = sum;
        }
        
        return answer;
    }
}

 

---

🕑 시간 복잡도

1️⃣ 이름 → 점수 매핑

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

 

name 배열을 한 번 순회하며 해시맵에 저장하는 부분의 시간 복잡도는 O(N)이다.

(여기서 N은 사람 수이고, 참고로 평균적으로 put은 O(1)이라고 한다.)

 

2️⃣ 사진별 합산

for (int i = 0; i < photo.length; i++) {
    int sum = 0;
    for (int j = 0; j < photo[i].length; j++) {
        String person = photo[i][j];
        sum += map.getOrDefault(person, 0);
    }
    answer[i] = sum;
}

 

모든 사진의 이름을 한 번씩 조회하는데, 각 조회는 평균 O(1)의 시간 복잡도를 가진다.

또한, 반복문 2개가 의미하는 것은 모든 사진에 등장하는 이름들의 총 합이므로,

사진 속 이름의 총 합을 P라고 뒀을 때 시간 복잡도는 O(P)이다.

(P = Σ photo[i].length 라고 보면 된다.)

 

👉🏻 따라서 최종 시간 복잡도는 O(N + P)이다.

      (이때 N은 name 배열에 있는 사람 수이고, P는 모든 사진에서 이름의 총합이다.)