프로그래머스 [연습문제 / 추억 점수](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 추억 점수

---

문제 링크: 문제 보기

문제 설명:

각 인물의 그리움 점수가 주어질 때, 여러 장의 사진에서 등장하는 인물들의 그리움 점수 합을 계산하는 문제입니다. 각 사진에 대해 포함된 인물들의 점수를 더해 리스트로 반환해야 합니다.

---

문제 해결 코드

#include <string>
#include <map>
#include <vector>

using namespace std;

map<string, int> mp; // 이름별 그리움 점수를 저장하는 맵

vector<int> solution(vector<string> name, vector<int> yearning, vector<vector<string>> photo) {
    vector<int> answer;
    
    // 이름별 그리움 점수를 맵에 저장
    for (int i = 0; i < name.size(); i++) {
        mp[name[i]] = yearning[i];
    }
    
    // 각 사진별로 점수 계산
    for (vector<string>& photo_group : photo) {
        int sum = 0;
        for (string& person : photo_group) {
            sum += mp[person]; // 존재하지 않는 이름은 기본값 0으로 처리됨
        }
        answer.push_back(sum);
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 해시맵(map)을 활용하여 각 인물의 그리움 점수를 저장한 후, 각 사진에 등장하는 인물들의 점수를 빠르게 합산합니다.
• 구현 세부사항:
• 이름과 그리움 점수를 map<string, int>에 저장하여 O(1) 시간에 접근할 수 있도록 합니다.
• 각 사진에서 등장하는 인물의 점수를 합산하여 answer 리스트에 추가합니다.
• 맵에 존재하지 않는 이름은 자동으로 0으로 처리됩니다.
• 시간 복잡도 분석:
• 이름-점수 매핑 저장: O(n), 여기서 n은 이름의 개수
• 각 사진별 점수 계산: O(p * m), 여기서 p는 사진의 개수, m은 사진에 포함된 인물 수
• 총 시간 복잡도: O(n + p * m)

---

결과

이 코드는 주어진 입력에 대해 효율적으로 각 사진별 점수를 계산하여 반환합니다. 해시맵을 이용해 빠르게 인물의 점수를 찾고 합산하는 방식으로 구현되었습니다.

다른 접근 방식으로는 unordered_map을 사용하여 탐색 성능을 O(1)로 개선할 수 있습니다. 하지만 이 문제에서는 일반 map을 사용해도 충분한 성능을 제공합니다.