대충 만든 자판

문제

문제 해석

*. 처음에는 그냥 한번만 순회하면 되는 줄 알고 풀었다가 5분 정도 날려먹었다.

1. 문자 1개가 각 키맵의 버튼을 대상으로 가장 작은 입력횟수를 찾아 입력횟수에 더해나간다.

2. 만약 가장 작은 입력횟수를 찾아나갈 때, 해당하는 키가 존재하지 않는다면 targets의 해당 원소는 완성될 수 없다.

3. 문자 1개씩 keymap의 각 원소에서 가장 작은 입력 횟수를 찾아나간다.

4. 갱신이 안 되었다면 이 Target은 완성할 수 없다.

코드

#include <string>
#include <vector>
#include <limits>

using namespace std;

constexpr int INT_MAX = numeric_limits<int>::max();

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    
    // targets[0]를 대상으로 생각해보면
    // 문자 1개가 각 키맵의 버튼을 대상으로 가장 작은 입력횟수를 찾아 입력횟수에 더해나간다.
    // 만약 가장 작은 입력횟수를 찾아나갈 때, 해당하는 키가 존재하지 않는다면 targets의 해당 원소는 완성될 수 없다.
    for(string& Target : targets)
    {
        int TargetTotalCount = 0;
        for(int TargetAlphaIDX = 0; TargetAlphaIDX < Target.length(); ++TargetAlphaIDX)
        {
            // 문자 1개씩 keymap의 각 원소에서 가장 작은 입력 횟수를 찾아나간다.
            int InputCount = INT_MAX;
            for(string& Key : keymap)
            {
                for(int IDX = 0; IDX < Key.length(); ++IDX)
                {
                    if(Key[IDX] == Target[TargetAlphaIDX])
                    {
                        if(IDX + 1 < InputCount)
                        {
                            InputCount = IDX + 1;
                        }
                        break;
                    }
                }
            }
            
            // 갱신이 안 되었다면 이 Target은 완성할 수 없다.
            if(InputCount == INT_MAX)
            {
                TargetTotalCount = -1;
                break;
            }
            
            TargetTotalCount += InputCount;
        }
        
        answer.push_back(TargetTotalCount);
    }
    return answer;
}

다른 사람의 풀이

1. map을 이용해 각 문자에 대한 최소한의 입력값을 찾아낸다. 최소한의 입력값이 0이 아니면 target을 완성해낼 수 있지만 0이 찾아지면 해당 문자열은 완성할 수 없으므로 -1을 배열에 담으면 된다.

 

회고

1. 시간 제한에 걸리지 않아서 풀 수 있었지만 앞으로는 map을 사용하는 습관을 들일 필요가 있다.