문제 설명
문자열 배열 arr가 주어졌을 때, 배열의 부분 수열(sub-sequence)을 연결하여 만든 문자열 s를 생각해 봅시다. 단, s는 중복 없는 고유한 문자들로만 구성되어야 합니다. 이때 s가 가질 수 있는 최대 길이를 구하는 것이 목표입니다.
예를 들어 입력이 ["cha", "r", "act", "ers"]라면 출력은 6이 됩니다. "chaers"와 "acters"처럼 각각 고유한 문자만으로 이루어진 길이 6짜리 문자열을 만들 수 있기 때문입니다.
접근 방법
이 문제는 브루트포스 방식으로 모든 가능한 조합을 탐색하면서 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
1. 두 문자열의 결합 가능 여부 확인 (ok 함수)
- 문자열 s와 t를 매개변수로 받는 ok() 메서드를 정의합니다.
- 맵(map) x를 하나 생성하여 각 문자의 등장 횟수를 기록합니다.
- s의 각 문자에 대해 카운트를 증가시키고, 어떤 문자의 카운트가 1을 초과하면 즉시 false를 반환합니다.
- t의 각 문자에 대해서도 동일하게 검사합니다.
- 모든 검사를 통과하면 true를 반환합니다. 즉, 두 문자열을 연결해도 중복 문자가 발생하지 않음을 의미합니다.
2. 최대 길이 탐색 (maxLength 메서드)
- 문자열 벡터 v를 만들고, 빈 문자열 하나를 삽입합니다. ans는 0으로 초기화합니다.
- 배열 arr의 각 문자열에 대해 다음을 반복합니다.
- v의 현재 크기를 n에 저장하고, v의 기존 원소들을 순회합니다.
- ok(v[j], arr[i])가 true라면, v[j]와 arr[i]를 연결한 새 문자열 t를 만들어 v에 추가하고, ans를 t의 길이와 비교하여 더 큰 값으로 갱신합니다.
이렇게 하면 지금까지 만든 모든 유효한 조합에 새 문자열을 붙여보면서, 중복 없이 연결 가능한 경우에만 결과 집합을 확장해 나갈 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(string s, string t){
map <char, int > x;
for(int i = 0; i < s.size(); i++){
x[s[i]]++;
if(x[s[i]] >1)return false;
}
for(int i = 0; i < t.size(); i++){
x[t[i]]++;
if(x[t[i]]>1)return false;
}
return true;
}
int maxLength(vector<string>& arr) {
vector <string> v;
int ans = 0;
v.push_back("");
for(int i = 0; i < arr.size(); i++){
int n = v.size();
for(int j = 0; j < n; j++){
if(ok(v[j],arr[i])){
string t = v[j]+arr[i];
v.push_back(t);
ans = max(ans,(int)t.size());
}
}
}
return ans;
}
};
main(){
vector<string> v = {"cha","r","act","ers"};
Solution ob;
cout << (ob.maxLength(v));
}실행 결과
입력
["cha","r","act","ers"]
출력
6
마무리
이 알고리즘은 완전 탐색 기반으로, 각 단계에서 이미 만들어진 유효한 부분 문자열들에 새 문자열을 덧붙일 수 있는지 검사합니다. 시간 복잡도는 문자열 개수와 각 조합 검사 비용에 비례하지만, 문제 제약 조건(알파벳 소문자 26자)상 충분히 실용적인 성능을 보입니다. 비트마스크(bitmask)를 활용하면 문자 중복 검사를 O(1)로 처리해 더욱 최적화할 수도 있습니다.