C++로 풀어보는 최소 고유 단어 약어(Minimum Unique Word Abbreviation)

문제 소개

"word"라는 문자열이 주어졌을 때, 이 문자열이 가질 수 있는 모든 약어는 다음과 같습니다.

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

여기서 목표 문자열(target)과 문자열들의 집합인 사전(dictionary)이 함께 주어집니다. 우리가 찾아야 하는 것은 사전에 있는 어떤 단어의 약어와도 충돌하지 않으면서, 길이가 가장 짧은 목표 문자열의 약어입니다. 약어에서 숫자와 문자는 각각 길이 1로 계산되므로, 예를 들어 "a32bc"의 길이는 4가 됩니다.

예를 들어 입력이 "apple"이고 사전이 ["blade"]라면, 정답은 "a4"입니다.

풀이 접근 방법

이 문제는 비트마스크(bitmask) 기법과 깊이 우선 탐색(DFS)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

목표 문자열과 길이가 같은 사전 단어만 고려합니다. 길이가 다른 단어와는 약어가 절대 충돌하지 않기 때문입니다.
문자열의 각 위치를 비트로 표현하여, 해당 위치의 문자를 유지할지(비트 1) 생략할지(비트 0) 결정합니다.
DFS로 후보 마스크를 탐색하면서, 사전의 모든 단어와 충돌하지 않는 최소 길이의 약어를 찾아냅니다.

알고리즘 단계

구체적인 풀이 과정은 다음과 같습니다.

abbrLen(mask) 함수 정의 : 마스크가 주어지면 해당 약어의 길이를 계산합니다. ret := n으로 초기화한 뒤, b := 3부터 시작해 b < bn 동안 b를 왼쪽 시프트하며, (mask AND b) == 0일 때마다 ret을 1씩 감소시킵니다. 이는 연속된 생략 구간이 하나의 숫자로 압축되는 규칙을 반영한 계산입니다.
dfs(bit, mask) 함수 정의 : 먼저 현재 마스크의 약어 길이(len)를 구하고, 이미 발견한 최솟값(minLen)보다 크거나 같으면 더 탐색하지 않고 가지치기합니다. 모든 사전 항목 d에 대해 (mask AND d) != 0이라면 충돌이 없는 것이므로 minLen := len, minab := mask로 갱신합니다. 충돌이 있다면 b := bit부터 b < bn까지 b를 두 배씩 늘려가며, (cand AND b) != 0인 비트에 대해 dfs(b*2, mask OR b)를 재귀 호출합니다.
메인 처리 로직 :
- ret := 빈 문자열, n := target의 길이, bn := 2^n, cand := 0, minLen := 무한대로 초기화합니다.
- 사전의 각 단어 s에 대해 길이가 n과 다르면 건너뜁니다. 길이가 같다면 각 위치에서 s[i] != target[i]인 인덱스를 word 비트에 기록하고, dict에 추가한 뒤 cand |= word로 후보 비트를 누적합니다.
- dfs(1, 0)을 호출해 최적의 마스크 minab을 구합니다.
- 마지막으로 minab을 기반으로 실제 약어 문자열을 만듭니다. 비트가 1인 위치는 target[i] 문자를 그대로 사용하고, 비트가 0으로 연속된 구간은 그 길이(i - j)를 숫자로 변환해 이어 붙입니다.

C++ 구현 예제

아래 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int n, cand, bn, minLen, minab;
    vector<int> dict;
    int abbrLen(int mask) {
        int ret = n;
        for (int b = 3; b < bn; b <<= 1) {
            if ((mask & b) == 0)
                ret--;
        }
        return ret;
    }
    void dfs(int bit, int mask) {
        int len = abbrLen(mask);
        if (len >= minLen)
            return;
        bool match = true;
        for (int d : dict) {
            if ((mask & d) == 0) {
                match = false;
                break;
            }
        }
        if (match) {
            minLen = len;
            minab = mask;
        }
        else {
            for (int b = bit; b < bn; b <<= 1) {
                if ((cand & b) != 0)
                    dfs(b << 1, mask | b);
            }
        }
    }
    string minAbbreviation(string target, vector<string> &dictionary) {
        string ret = "";
        n = target.size();
        bn = 1 << n;
        cand = 0;
        minLen = INT_MAX;
        for (string &s : dictionary) {
            if (s.size() != n)
                continue;
            int word = 0;
            for (int i = 0; i < s.size(); i++) {
                if (s[i] != target[i])
                    word |= (1 << i);
            }
            dict.push_back(word);
            cand |= word;
        }
        dfs(1, 0);
        for (int i = 0; i < n;) {
            if ((minab & (1 << i)) != 0) {
                ret += target[i];
                i++;
            }
            else {
                int j = i;
                while (i < n && (minab & (1 << i)) == 0)
                    i++;
                ret += to_string(i - j);
            }
        }
        return ret;
    }
};
main() {
    Solution ob;
    vector<string> v = {"blade"};
    cout << (ob.minAbbreviation("apple",v));
}

실행 결과

입력

"apple", {"blade"}

출력

a4

마무리

이 풀이는 비트마스크로 각 문자의 유지 여부를 표현하고, DFS와 가지치기를 활용해 사전과 충돌하지 않는 최소 길이의 고유 약어를 효율적으로 찾아냅니다. 탐색해야 할 마스크는 최대 2^n개이며, 각 단계에서 사전과의 충돌 여부를 비트 연산으로 빠르게 판단하기 때문에 문자열 길이가 짧은 경우 매우 효과적으로 동작합니다.