[LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters

문제 출처: https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

Maximum Length of a Concatenated String with Unique Characters - LeetCode

---

문제

문자열 배열 arr이 주어진다. 문자열 s는 유일한 문자를 갖는 arr의 하위 시퀀스의 연결이다.

 

s의 가능한 최대 길이를 반환하라.

예제

Input: arr = ["un","iq","ue"]
Output: 4

Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Input: arr = ["cha","r","act","ers"]
Output: 6

Explanation: Possible solutions are "chaers" and "acters".

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

---

풀이

문제에서 요구하는 결과가 특정 조건을 만족하는 배열의 "조합"을 구하는 것이라는 것을 알 수 있습니다. 여기서 특정 조건이라는 것은 중복된 문자가 존재해서는 안된다는 것입니다.

 

조합을 구하기 위해 백트래킹 또는 단순 재귀를 이용한 방법을 이용할 수 있습니다. 여기서는 단순 재귀를 이용한 방법을 사용하고자 합니다. 일반적으로 재귀를 이용하여 가능한 모든 조합의 경우를 담아내는 함수를 작성한다고 할 때 다음과 같은 코드를 작성할 수 있습니다.

// arr: 입력 배열, pos: 선택 여부를 결정할 인덱스
// tmpResult: 현재 선택된 원소들이 연결된 문자열
// result: 가능한 모든 케이스의 결과가 담긴 배열
var findCombination = function(arr, pos, tmpResult ,result) {
    if (pos == arr.length) {
    	result.push(tmpResult);
        return;
    }
    
    // arr[pos]를 선택하지 않는 케이스
    findCombination(arr, pos+1, tmpResult, result);
    
    // arr[pos]를 선택하는 케이스
    findCombination(arr, pos+1, tmpResult + arr[pos], result);
}

이 코드를 변형하여 문제에서 요구하는 특별한 조건을 만족하는 조합을 찾아낼 수 있도록 할 수 있습니다.

 

문제에서 이야기하는 특별한 조건인 "유일한 문자"로 구성된 조합을 찾아내기 위해서 코드의 수정(혹은 추가)을 고려해야 하는 부분은 arr[pos]를 선택하는 부분입니다. arr[pos]를 선택하고 이전 단계의 결과에 합치는 과정에서 중복된 문자가 생겨날 수 있기 때문입니다.

 

두 문자열에 중복된 문자가 존재하는지 비교를 위해 Map 자료구조를 이용할 수 있습니다. 특별한 자료구조 없이 단순 반복문을 이용한 비교도 가능한 방법이지만, 이후 단계에서 반복적으로 비교가 이루어지는 것을 생각할 때, 특정 문자가 존재하는지 여부를 O(1)의 시간 복잡도로 수행할 수 있는 Map 구조를 활용하는 것이 좋을 것이라는 판단을 하였습니다.

// arr: 입력 배열, pos: 선택 여부를 결정할 인덱스
// tmpCompose: 현재 선택된 원소들의 문자 구성이 담긴 Map
var findCombination = function(arr, pos, tmpCompose) {
    if (pos == arr.length) {
        return tmpCompose.size;
    }
    
    // arr[pos]를 선택하지 않는 케이스
    tmpMaxLength = findCombination(arr, pos+1, tmpCompose);
    
    // arr[pos] 선택 전, 중복 문자 체크
    const tmp = new Map(tmpCompose);
    for (let i = 0; i < arr[pos].length; i++) {
    	if (tmp.has(arr[pos][i])) {
        	return tmpMaxLength;
        }
        
        tmp.set(arr[pos][i], 1);
    }
    // arr[pos]를 선택하는 케이스
    tmpMaxLength = Math.max(tmpMaxLength, findCombination(arr, pos+1, tmp));
    
    return tmpMaxLength;
}

이 코드에서 핵심은 arr[pos]를 선택하기 전에, 이전에 선택했던 문자들과 중복 문자가 있는지를 체크하는 것입니다. 만약 중복된 문자가 있다면, 그 순간 탐색을 끝냅니다.

 

또 다른 코드의 변화는 반환 형태입니다. 현재 코드는 재귀를 반복하다가 pos가 arr.length가 되는 순간에 tmpCompose의 크기를 반환합니다. 그리고 반환된 값들 중, 더 큰 값을 반환하는 형태로 재귀의 결과가 취합됩니다.

 

다음과 같이 위 함수를 호출하는 것으로 문제에 대한 답을 얻을 수 있습니다.

var maxLength = function(arr) {
    let answer = 0;
    
    answer = findCombination(arr, 0, new Map());
    
    return answer;
};

시간 복잡도에 대해서 생각해보면, 조합을 구하는 재귀 함수에서 O($2^n$)의 시간 복잡도가 걸립니다. 또한 재귀의 안에 중복 체크를 위한 반복문이 있기 때문에 이 또한 계산을 해줘야 합니다. 다만, 이 문제에서는 각 arr[i]의 문자열의 길이가 26 이하로 제한되어 있기 때문에 이 반복문의 시간은 최악의 경우를 상정해도 매 단계마다 상수의 시간이 걸리게 되므로 O(1)입니다.

 

최종적으로 이 알고리즘의 시간복잡도는 O($2^n$)입니다.

 

Github: 1239.js

GitHub - opwe37/Algorithm-Study