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

문제 이름 : 추억 점수

1. 문제 설명

2. 매개 변수

이렇게 3가지 매개변수가 있는데 여기서 name과 yearning의 크기는 같고 각각의 순서에 대응되는 값이기 때문에 map<string, int> 자료구조를 사용하면 훨씬 편하게 정리할 수 있다. 그리고 map을 사용하면 장점이 결국 문제가 2차원 배열인 photo를 돌면서 name을 탐색하고 name에 맞는 점수를 더해주는 문제인데 탐색을 map 방식으로 바꾸게 되면 시간복잡도를 줄일 수 있다.

3. Solution

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

using namespace std;

vector<int> solution(vector<string> name, vector<int> yearning, vector<vector<string>> photo) {
    vector<int> answer;
    map<string, int> scoreMap;
    
    //map initialize
    for(int i=0;i<name.size();i++){
        scoreMap[name[i]] = yearning[i];
    }
    
    //search photo & score count
    for(int i=0;i<photo.size();i++){
        int scoreCnt = 0;
        for(int j=0;j<photo[i].size();j++){
            scoreCnt += scoreMap[photo[i][j]];
        }
        answer.push_back(scoreCnt);
    }
    
    return answer;
}

우선 map 자료구조를 사용하기 때문에 map에 해당하는 값을 Key에 name을 Value에 Yearning을 넣어서 초기화 해준다. 그리고 photo가 2차원배열이기 때문에 이중 for문을 돌면서 탐색을 하는데 이때 score를 누적하는 변수를 선언해주고 scoreMap에 photo안의 값을 넣어 나오는 Value를 누적해준다. 이때 name vector에 없는 값이 들어오면 0을 더해주어야 하는데 map은 없는 ket가 들어오면 해당 key를 insert하고 value는 int기 때문에 0으로 초기화 된다. 따라서 0을 더해주게 되고 다음 번에 또 같은 key가 호출이 되더라도 이미 0으로 초기화가 되어있기 때문에 0점을 더해준다. 

4. review

이 문제는 만약 map을 사용하지 않고 vector를 그대로 사용하게 되면 해당 이름이 있는지 find하는 과정에서 O(N)의 복잡도를 가지는데 map을 사용하면 정렬된 Data를 탐색하기 때문에 O(logN)의 복잡도를 가진다. 따라서 2차원 배열인 photo를 탐색하는 것까지 하면 O(N^3)과 O(N^2logN)으로 차이가 벌어진다. 그리고 map에서 [] operator는 없는 key 값이 들어오면 key를 자동으로 insert해버린 다는 점이 굉장히 불안정하고 예상치 못한 동작을 이끌어내는 방식이라 find가 권장되지만 이 문제같은 경우는 없는 경우 0을 더해주는 것이 맞기 때문에 굳이 find를 쓰지 않고 [] operator로 코드를 단순화 시킬 수 있다.

 

GitHub - leejy811/AlgorithmStudy: 코딩 테스트 스터디