[프로그래머스] [연습문제] 추억 점수(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "추억 점수 계산하기" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 여러 사진 속에서 그리워하는 사람들의 그리움 점수를 합산하여 각 사진의 추억 점수를 계산하는 문제입니다. 문제를 해결하기 위한 알고리즘과 코드를 자세히 알아보겠습니다.

문제링크 : 

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

프로그래머스

문제 개요

주어진 문제에서는 사진별로 추억 점수를 계산해야 합니다. 각 사진에는 여러 사람이 등장하며, 각 사람은 그리움 점수를 가지고 있습니다. 추억 점수는 해당 사진에 등장하는 모든 사람의 그리움 점수를 합산한 값이 됩니다. 예를 들어, 사진에 등장하는 사람의 이름과 그리움 점수가 주어졌을 때, 그리움 점수를 모두 합산하여 해당 사진의 추억 점수를 계산합니다.

문제 해결 방법

이 문제를 해결하기 위해서는 다음과 같은 단계를 따라갑니다.

1. 각 사람의 이름과 그리움 점수를 매칭시키기 위해 name 배열과 yearning 배열을 사용하여 name_yearning 맵을 생성합니다.
2. 각 사진 별로 추억 점수를 계산합니다. 이를 위해 사진 배열 photo를 순회하면서 다음을 수행합니다.
3. 모든 사진에 대한 추억 점수를 계산한 후, answer 배열을 반환합니다.

코드 구현

문제를 해결하기 위한 코드는 다음과 같습니다. C++을 사용하여 작성되었으며, 주석을 통해 코드의 각 부분을 설명하였습니다.

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<string> name, vector<int> yearning, vector<vector<string>> photo) {
    vector<int> answer;
    map<string, int> name_yearning;
    int sum = 0;

    // 각 사람의 이름과 그리움 점수를 매칭시키는 맵을 생성합니다.
    for (int i = 0; i < name.size(); i++) {
        name_yearning[name[i]] = yearning[i];
    }

    // 각 사진 별로 추억 점수를 계산합니다.
    for (int i = 0; i < photo.size(); i++) {
        sum = 0;
        for (int j = 0; j < photo[i].size(); j++) {
            // 각 사람의 이름을 확인하고, 그리움 점수를 맵에서 조회합니다.
            if (name_yearning[photo[i][j]] != 0) {
                sum += name_yearning[photo[i][j]];
            }
        }
        // 각 사진의 추억 점수를 answer 배열에 추가합니다.
        answer.push_back(sum);
    }

    return answer;
}

결과 및 시간 복잡도

주어진 예제에 대한 결과를 확인하면 문제를 정확하게 해결하는 것을 확인할 수 있습니다. 이 알고리즘의 시간 복잡도는 입력으로 주어진 photo 배열의 길이와 각 배열의 원소의 길이에 비례하며, 모든 사진에 대해 그리움 점수를 계산하므로 최악의 경우에도 photo 배열의 길이만큼의 연산을 수행합니다. 따라서 시간 복잡도는 O(N)이며, N은 photo 배열의 길이입니다.