프로그래머스 - 대충 만든 자판 (C++)

프로그래머스

 

문제를 슥 보면 단순하게는 keymaps와 targets를 모두 순회하면 될 것 같습니다. 실제로 그렇게 하면 테스트케이스는 풀리겠지만, 이렇게 구현하게 되면 4중 for문 구조를 사용해야 됩니다. keymap의 개수와 길이, targets의 개수와 길이는 모두 100이고, 4중 for문으로 구현시 단순 시간 복잡도가 N^4가 되기 때문에 최악의 경우에는 무시할 수 없는 수의 계산이 필요합니다. 따라서 이 해결방법은 권장되지 않습니다.

---

keymaps는 결국은 알파벳에 대한 정보를 담고 있고, 매 targets를 계산할때마다 각 알파벳을 누르기 위한 최소 값은 동일합니다(=재활용이 가능합니다). 그러므로 keymaps만 1차적으로 순회하면서 각 알파벳을 누르기 위한 최소 값을 저장합니다.

unordered_map<char, int> costMap;
    
for(int i = 0; i < keymap.size(); i++) {
    for(int j = 0; j < keymap[i].length(); j++) {
        auto exist = costMap.find(keymap[i][j]);
        if(exist == costMap.end()) {
            costMap[keymap[i][j]] = j+1;
        } else {
            auto currentCost = costMap[keymap[i][j]];
            costMap[keymap[i][j]] = min(currentCost, j+1);
        }
    }
}

map 대신 unordered_map를 사용하는 이유는 key의 개수가 최대값이 정해져있고(26개), 순차적으로 정렬할 필요는 없기 때문입니다.

이렇게 우리는 각 알파벳별 최소 비용 정보가 담긴 map을 얻었습니다.

 

이제 targets를 순회합니다.

for(int i = 0; i < targets.size(); i++) {
    auto totalCost = 0;
    bool impossible = false;
    for(auto c : targets[i]) {
        auto exist = costMap.find(c);
        if(exist == costMap.end()) {
            impossible = true;
            break;
        }
        totalCost += costMap[c];
    }
    if(impossible) answer.push_back(-1);
    else answer.push_back(totalCost);
}

targets의 각 알파벳별 비용을 계산해서 제일 바깥쪽의 for문이 종료될때마다 answer vector에 push_back해줍니다.

이때 불가능한 알파벳이 있는지 확인하고, 있다면 -1을 push_back합니다.

사실 map에 알파벳을 미리 넣어두고 초기값을 -1로 한 뒤에 targets 순회 과정에서 값이 -1이면 break하는 방법이나, 애초에 map에 저장하지 않고 vector에 알파벳별 최소값을 저장한다거나(그럼 이때는 '알파벳'-'A' 연산으로 0,1,2번 인덱스에 값을 넣게 될 것입니다) 하는 방법을 통해 targets 순회문을 간소화 할 수 있을것입니다. 저는 문제풀때는 이정도까지 생각이 안나서요. 최대한 직관적으로 풀었습니다.

 

이렇게 answer에는 각 target별 비용이 계산되어 추가됩니다. 리턴해주면 됩니다.

아래는 전체 코드입니다.

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

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    map<char, int> costMap;
    
    for(int i = 0; i < keymap.size(); i++) {
        for(int j = 0; j < keymap[i].length(); j++) {
            auto exist = costMap.find(keymap[i][j]);
            if(exist == costMap.end()) {
                costMap[keymap[i][j]] = j+1;
            } else {
                auto currentCost = costMap[keymap[i][j]];
                costMap[keymap[i][j]] = min(currentCost, j+1);
            }
        }
    }
    
    for(int i = 0; i < targets.size(); i++) {
        auto totalCost = 0;
        bool impossible = false;
        for(auto c : targets[i]) {
            auto exist = costMap.find(c);
            if(exist == costMap.end()) {
                impossible = true;
                break;
            }
            totalCost += costMap[c];
        }
        if(impossible) answer.push_back(-1);
        else answer.push_back(totalCost);
    }
    
    
    return answer;
}