[프로그래머스/Level 1] 대충 만든 자판

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

프로그래머스

 

keymap의 각 알파벳 별 순서를 map에 저장한 후, targets의 문자열을 만들 수 있는 최소 클릭 수를 구하였다.

이때 주어진 keymap에서 특정 문자열을 만들 수 없는 경우 -1을 리턴해야 하는데, 다음 케이스를 조심해야 한다.

 

keymap : ["BC"]

targets : ["AC", "BC"]

return : [-1, 3]

 

=> "BC"는 만들 수 있으므로 -1로 리턴하면 안된다. 따라서 이를 구분하기 위해 flag 값을 추가

 

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    int size = keymap.size();
    unordered_map<char, int> m[size];
    
    for (int i = 0; i < keymap.size(); i++) {
        for (int j = 0; j < keymap[i].size(); j++) {
            if (m[i][keymap[i][j]] != 0) continue;
            m[i][keymap[i][j]] = j + 1;
        }
    }

    for (int k = 0; k < targets.size(); k++) {
        int sum = 0;
        bool isPossible = true;
        
        for (int i = 0; i < targets[k].size(); i++) {
            char ch = targets[k][i];
            int minCnt = 2147000000;
            
            for (int j = 0; j < size; j++) {
                if (m[j][ch] == 0) continue;
                minCnt = min(minCnt, m[j][ch]);
            }
            
            if (minCnt == 2147000000) {
                isPossible = false;
                break;
            }
            
            sum += minCnt;
        }
        
        if (isPossible) answer.push_back(sum);
        else answer.push_back(-1);
    }
    
    return answer;
}