문제 개요
문자열 배열 words가 주어졌을 때, 서로 공통된 문자를 갖지 않는 두 단어 word[i]와 word[j]에 대해 length(word[i]) × length(word[j]) 값의 최댓값을 구하는 것이 목표입니다. 모든 단어는 영어 소문자로만 이루어져 있다고 가정하며, 조건을 만족하는 두 단어가 존재하지 않으면 0을 반환합니다.
예를 들어 입력이 ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]라면 출력은 16입니다. 그 이유는 "abcw"와 "xtfn"이 공통 문자를 하나도 공유하지 않으면서 각각 길이가 4이므로, 4 × 4 = 16이 최댓값이 되기 때문입니다.
풀이 접근 방식: 비트마스크(Bitmask)
두 단어가 공통 문자를 갖는지 확인하는 가장 효율적인 방법은 각 단어를 26비트 정수(비트마스크)로 표현하는 것입니다. 알파벳 소문자 'a'부터 'z'까지를 각각 비트 위치 0~25에 매핑하고, 단어에 해당 문자가 포함되어 있으면 그 비트를 1로 설정합니다. 이렇게 하면 두 비트마스크의 AND 연산 결과가 0일 때, 즉 공통으로 켜진 비트가 없을 때 두 단어 사이에 공통 문자가 없다는 것을 단 한 번의 연산으로 판별할 수 있습니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 단어 배열의 크기를 n이라 할 때, 인덱스를 키로 갖는 맵 m을 준비합니다.
- i = 0부터 n − 1까지 반복하면서 각 단어 s = words[i]에 대해 다음을 수행합니다.
- key := 0으로 초기화
- 단어의 모든 문자 s[j]에 대해 key := key OR 2^(s[j] − 'a'의 ASCII 값 차이) 연산을 적용해 문자 존재 여부를 비트에 기록
- m[i] := key로 저장 - 결괏값 ret := 0으로 초기화합니다.
- j > i인 모든 단어 쌍 (i, j)에 대해 m[i] AND m[j] == 0이면, 즉 공통 문자가 없으면 ret := max(ret, length(words[i]) × length(words[j]))로 갱신합니다.
- ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 전체 로직을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxProduct(vector<string>& words) {
// 각 단어를 26비트 마스크로 변환해 저장
unordered_map <int, int> m;
int n = words.size();
for(int i = 0; i < n; i++){
string s = words[i];
int key = 0;
for(int j = 0; j < s.size(); j++){
key |= 1 << (s[j] - 'a');
}
m[i] = key;
}
int ret = 0;
// 공통 문자가 없는 모든 단어 쌍을 검사
for(int i = 0; i < words.size(); i++){
for(int j = i + 1; j < words.size(); j++){
if((m[i] & m[j]) == 0){
ret = max(ret, (int)words[i].size() * (int)words[j].size());
}
}
}
return ret;
}
};
int main(){
Solution ob;
vector<string> v = {"abcw","baz","foo","bar","xtfn","abcdef"};
cout << (ob.maxProduct(v));
}
입력
["abcw","baz","foo","bar","xtfn","abcdef"]
출력
16
복잡도 분석
비트마스크 생성 단계는 전체 문자 수에 비례하므로 O(N × L)(N은 단어 개수, L은 평균 단어 길이)이고, 모든 단어 쌍을 비교하는 단계는 O(N²)입니다. 따라서 전체 시간 복잡도는 O(N² + N × L)이며, 맵에 마스크를 저장하기 위한 추가 공간 복잡도는 O(N)입니다. 문자를 하나씩 직접 비교하는 방식(O(N² × L))과 달리 각 쌍의 비교가 상수 시간에 이루어지므로, 실질적으로 훨씬 빠르게 동작합니다.