<프로그래머스 C++> 휴대폰 자판 풀이

문제 설명

휴대폰 자판은 하나의 키에 여러 문자가 할당될 수 있다. 특정 키를 연속으로 누르면 할당된 순서대로 문자가 바뀐다.

 

keymap과 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return해라.

 

단, 목표 문자열을 작성할 수 없을 때는 -1을 return해라.

 

예시

keymap	targets	result
["ABACD", "BCEFD"]	["ABCD","AABB"]	[9, 4]
["AA"]	["B"]	[-1]
["AGZ", "BSSS"]	["ASA","BGZ"]	[4, 6]

---

문제 흐름 파악

1. 같은 문자가 여러 키에 존재할 수 있다. 따라서 각 문자마자 최소 입력 횟수를 미리 계산해둬서 꺼내쓴다.

 

2. keymap을 전부 순회하면서 알파벳 26개에 대한 최솟값을 벡터에 저장한다.

 

3. targets를 순회하면서 각 문자의 최솟값을 합산한다. 중간에 입력 불가능한 문자가 나오면 -1을 저장한다.

---

문제 풀이

#include <string>
#include <vector>
using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    vector<int> ans(26, -1);

    for(int i = 0; i < keymap.size(); i++)
        for(int j = 0; j < keymap[i].size(); j++)
        {
            char c = keymap[i][j];
            int cost = j + 1;
            if(ans[c - 'A'] == -1 || cost < ans[c - 'A'])
                ans[c - 'A'] = cost;
        }

    for(int i = 0; i < targets.size(); i++)
    {
        int total = 0;
        bool possible = true;

        for(int j = 0; j < targets[i].size(); j++)
        {
            char c = targets[i][j];
            if(ans[c - 'A'] == -1)
            {
                possible = false;
                break;
            }
            total += ans[c - 'A'];
        }

        answer.push_back(possible ? total : -1);
    }

    return answer;
}

---

코드 흐름

1. ans 벡터 초기화

vector<int> ans(26, -1);

알파벳 26개에 대한 최소 입력 횟수를 저장할 벡터이다.

 

-1로 초기화해서 앚기 찾지 못한 문자를 -1로 저장한다. 

 

2. keymap 순회 - 최솟값 계산

char c = keymap[i][j];
int cost = j + 1;
if(ans[c - 'A'] == -1 || cost < ans[c - 'A'])
    ans[c - 'A'] = cost;

j 번째 문자에서 j+1번 눌러야 하므로, cost에 j+1을 저장한다.

 

ans[c - 'A']로 알파벳을 0~25의 인덱스로 변환한다.

조건문에서 두 가지 조건일 때 업데이트 한다.

 

1. ans[c-'A'] == -1 : 한 번도 찾지 못한 문자일 때, 무조건 저장한다.

2. cost < ans[c - 'A'] : 더 작은 값이 나오면 교체

 

3. targets 순회 - 합산

if(ans[c - 'A'] == -1)
{
    possible = false;
    break;
}
total += ans[c - 'A'];

각 문자의 최솟값을 꺼내서 합산한다.

 

중간에 -1인 문자가 나오면 즉시 break하고 possible = false로 표시한다.

 

4. 결과 저장

answer.push_back(possible ? total : -1);

possible이 true이면 합산 값을, false라면 -1을 저장한다.

---

핵심 포인트

1. 각 문자의 최소 입력 횟수를 미리 계산해두면 targets 순회가 단순해진다.

 

2. [c - 'A']로 알파벳을 인덱스로 변환해서 벡터에 시간복잡도 O(1)로 접근한다.