[프로그래머스/Day 20] 대충 만든 자판 - 전처리의 중요성

1. 문제 분석 및 핵심 조건

이 문제는 여러 개의 문자가 할당된 자판에서 특정 문자열을 만들기 위한 최소 누적 타수를 구하는 문제입니다.

• 핵심 제약: 동일한 문자가 여러 키(Key)에 존재할 수 있으며, 각 키에서도 위치(인덱스)가 다릅니다.
• 목표: 각 문자를 입력할 수 있는 가장 적은 횟수를 찾아 합산하되, 하나라도 입력 불가능하면 -1을 반환해야 합니다.
• 데이터 규모: 키맵과 타겟의 크기가 크지 않아 시간 복잡도보다는 논리적 정확성이 우선시되는 문제입니다.

---

2. 초기 접근 및 시행착오

처음에는 targets를 순회하며 실시간으로 keymap의 요소들을 find() 함수로 찾는 방식을 시도했습니다.

• 실패했던 지점: targets[i]를 처리할 때 단순히 인덱스가 같은 keymap[i]만 검사하는 실수를 범했습니다. 모든 키맵을 뒤져야 한다는 점을 간과하여 논리적 오류가 발생했습니다.
• 복잡도 문제: 매번 모든 키맵을 다시 검색하면 루프가 3중, 4중으로 겹치게 되어 코드가 읽기 어려워지고 머릿속이 복잡해지는 현상이 나타났습니다.

---

3. 해결 전략

복잡한 루프를 해결하기 위해 '전처리(Preprocessing)' 단계를 도입했습니다.

1. 최소 타수 사전 구축: std::map<char, int>를 사용하여 알파벳 'A'부터 'Z'까지 각각의 글로벌 최소 타수를 미리 계산합니다.
2. 단일 루프로 합산: 생성된 사전을 이용하면 targets를 순회할 때 단 한 번의 조회( 또는 )만으로 필요한 타수를 얻을 수 있습니다.
3. 예외 처리: 사전에 없는 문자가 등장하는 즉시 플래그를 사용하여 해당 문자열 전체를 -1로 처리합니다.

---

4. 코드 구현

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

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    map<char, int> minPress;

    // 1. 전처리: 모든 keymap을 분석해 각 문자의 최소 타수 계산
    for (const string& key : keymap) {
        for (int i = 0; i < key.size(); ++i) {
            char c = key[i];
            if (minPress.find(c) == minPress.end()) {
                minPress[c] = i + 1;
            } else {
                minPress[c] = min(minPress[c], i + 1);
            }
        }
    }

    // 2. targets를 돌며 총합 계산
    for (const string& target : targets) {
        int total = 0;
        bool possible = true;

        for (char c : target) {
            if (minPress.find(c) != minPress.end()) {
                total += minPress[c];
            } else {
                // 키맵에 없는 문자가 있다면 바로 실패
                possible = false;
                break;
            }
        }
        
        answer.push_back(possible ? total : -1);
    }

    return answer;
}

---

5. 복기 및 확장

이번 문제를 통해 얻은 가장 큰 교훈은 "데이터를 가공해서 쓰기 편한 형태로 만드는 것이 코딩의 절반이다"라는 점입니다. 단순히 루프를 돌리는 것을 넘어, 왜 '전처리'가 알고리즘의 핵심 패턴인지 정리해 보았습니다.

전처리 기법이 중요한 이유와 알고리즘적 확장성

1. 탐색을 조회로 변환 (해시와의 연결)
   • 이 문제에서 전처리를 하지 않으면 타겟 문자가 나올 때마다 매번 키맵을 뒤져야 하는 탐색(Search) 문제가 됩니다.
   • 하지만 미리 최소 타수 사전을 만들어두면 단 한 번의 접근으로 답을 얻는 조회(Lookup) 문제로 변환됩니다. 이는 해시(Hash) 자료구조를 사용하는 가장 근본적인 목적이자, 시간 복잡도를 $O(N)$에서 $O(1)$로 떨어뜨리는 마법입니다.
2. 최적 부분 구조의 활용 (DP와의 연결)
   • 동적 계획법(DP)의 핵심은 "작은 문제의 해를 저장하고 이를 재활용하는 것"입니다.
   • 이번 문제에서 '각 알파벳의 최소 타수'를 미리 구해둔 것은, 전체 문자열의 타수를 구하기 위한 최적의 부분 해를 사전에 정의한 것과 같습니다. 이처럼 작은 단위의 최적값을 저장(Memoization)해 나가는 습관은 복잡한 DP 문제를 푸는 사고의 밑거름이 됩니다.
3. 트레이드오프(Trade-off)의 이해
   • 전처리는 약간의 공간(Memory)을 더 사용하는 대신, 실행 시간(Time)을 획기적으로 단축하는 기술입니다.
   • "한 번 메모리를 써서 정리해두면 이후 모든 과정이 편해진다"는 이 트레이드오프 전략은 실무에서 대규모 데이터를 처리할 때도 가장 기본이 되는 설계 원칙입니다.

"시간을 아끼기 위해 메모리를 빌려 쓰는 기술, 그것이 전처리의 핵심입니다."

마치며

처음에는 단순히 루프를 어떻게 돌릴지 고민했지만, "내가 정보를 어떤 형태로 가지고 있어야 가장 편하게 꺼낼 수 있을까?"를 먼저 고민하니 코드가 훨씬 간결해졌습니다. 앞으로도 복잡한 조건이 붙은 문제를 만나면, 무작정 코드를 쓰기보다 데이터를 먼저 '요약'하는 습관을 들여야겠습니다.