[C++] 프로그래머스 대충 만든 자판 [해쉬, Hash]

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

프로그래머스

풀이

타겟 문자를 만드는데 필요한 최소 클릭 횟수를 반환하는 문제입니다.

keymap에서 등장하는 각 문자를 최소 클릭 횟수로 해싱하면 답을 쉽게 구할 수 있습니다. 

즉,  keymap이 ["ABACD", "BCEFD"] 일때, A:1, B:1, C:2, D:5 ... 이런식으로 최소 클릭 횟수로 해싱됩니다.

해싱이 끝나면 타겟 문자에 대해 해싱값에 접근하면 되고, 이 때 해싱된 값이 0 이면 해당 문자는 keymap에 없었다는 의미이므로 만들 수 없는 문자열입니다.

따라서 break한 후 -1을 넣어줍니다.

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

int maxKeySize;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    unordered_map<char, int> hash;
    // 최소 클릭 횟수로 해싱
    for (auto& i:keymap) {
        for (int j=0; j<i.size(); j++){
            if (hash[i[j]]!=0 && hash[i[j]]>j+1)
                hash[i[j]]=j+1;
            else if (!hash[i[j]]) hash[i[j]]=j+1;
        }
    }
    // 타겟 문자열 클릭 횟수 구하기
    for (auto& i:targets){
        int sum=0;
        for (int j=0; j<i.size(); j++){
        	// 키맵에 없는 경우
            if (!hash[i[j]]) {
                sum=-1;
                break;
            }
            else sum+=hash[i[j]];
        }
        answer.push_back(sum);
    }
    
    return answer;
}