프로그래머스 [연습문제 / 대충 만든 자판](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 대충 만든 자판

---

문제 링크: 문제 보기

문제 설명:

각 키에 여러 개의 문자가 할당된 자판이 주어졌을 때, 주어진 단어를 입력하는 데 필요한 최소 키 입력 횟수를 구하는 문제입니다. 특정 문자를 입력할 수 없는 경우 -1을 반환해야 합니다.

---

문제 해결 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int alpha[26]; // 각 알파벳의 최소 입력 횟수 저장

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    
    // 각 문자에 대한 최소 입력 횟수 초기화
    fill(alpha, alpha + 26, 1e9);
    
    for (string &key : keymap) {
        for (int j = 0; j < key.size(); j++) {
            alpha[key[j] - 'A'] = min(alpha[key[j] - 'A'], j + 1);
        }
    }
    
    // 목표 단어 입력 횟수 계산
    for (string &target : targets) {
        int sum = 0;
        for (char ch : target) {
            if (alpha[ch - 'A'] == 1e9) { // 입력 불가능한 문자
                sum = -1;
                break;
            }
            sum += alpha[ch - 'A'];
        }
        answer.push_back(sum);
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 주어진 키맵을 분석하여 각 알파벳에 대해 최소 입력 횟수를 미리 계산한 후, 이를 활용해 목표 단어 입력 횟수를 효율적으로 구합니다.
• 구현 세부사항:
• alpha 배열을 사용해 각 문자의 최소 입력 횟수를 저장합니다.
• 각 키맵을 순회하며, 해당 문자가 등장하는 가장 빠른 위치(=최소 키 입력 횟수)를 기록합니다.
• 목표 단어를 구성하는 문자의 입력 횟수를 합산하여 answer에 저장합니다.
• 입력할 수 없는 문자가 있는 경우 -1을 반환합니다.
• 시간 복잡도 분석:
• 키맵 분석: O(K * L), 여기서 K는 키맵 개수, L은 각 키맵의 길이
• 목표 단어 계산: O(T * M), 여기서 T는 목표 단어 개수, M은 단어의 평균 길이
• 총 시간 복잡도: O(K * L + T * M)

---

결과

이 코드는 주어진 키맵을 기반으로 최소 키 입력 횟수를 계산하여 목표 단어를 입력하는 데 필요한 총 횟수를 반환합니다. 사전 처리 과정을 활용해 빠르게 정답을 도출할 수 있도록 최적화되었습니다.

다른 접근 방식으로는 unordered_map을 사용하여 문자의 최소 입력 횟수를 저장하는 방법이 있으며, 이는 탐색 속도를 개선할 수 있습니다.