파이썬으로 공통 문자가 없는 두 단어의 최대 길이 합 구하기

문제 개요

소문자 알파벳으로만 이루어진 문자열 리스트 words가 주어졌을 때, 서로 공통된 문자를 하나도 가지지 않는 두 단어를 골라 그 길이의 합이 최대가 되도록 만드는 프로그램을 작성해 보겠습니다.

예를 들어 입력이 ["abcd", "mno", "abdcmno", "amno"]라고 한다면, 공통 문자가 전혀 없는 단어 쌍은 "abcd"와 "mno"입니다. 이때 길이의 합은 4 + 3 = 7이므로 출력값은 7이 됩니다.

접근 방식: 비트마스크(Bitmask) 활용

두 단어에 공통 문자가 있는지 확인하는 가장 직관적인 방법은 모든 문자를 일일이 비교하는 것이지만, 이는 비효율적입니다. 대신 비트마스크 기법을 사용하면 각 단어를 하나의 26비트 정수로 압축해서 표현할 수 있습니다.

알파벳은 총 26자이므로, 단어에 포함된 각 문자를 해당 위치의 비트(1 << (문자 - 'a'))로 설정하면 됩니다. 이렇게 만든 두 비트마스크를 AND 연산했을 때 결과가 0이라면, 두 단어 사이에 겹치는 문자가 하나도 없다는 의미입니다.

풀이 절차

1. sign() 함수를 정의합니다. 이 함수는 단어를 받아 26비트 정수 형태의 시그니처를 반환합니다.
2. 초기값 value = 0으로 설정한 뒤, 단어의 각 문자 c에 대해 value를 (1 << (ord(c) - ord('a')))와 OR 연산합니다.
3. 모든 문자를 처리한 후 value를 반환합니다.
4. 메인 로직에서는 리스트의 모든 단어에 대해 시그니처를 계산하여 signature 배열에 저장합니다.
5. 정답 변수 ans를 0으로 초기화하고, 모든 단어 쌍 (i, j)에 대해 signature[i] & signature[j] == 0인 경우 두 단어 길이의 합으로 ans를 갱신합니다.
6. 최종적으로 ans를 반환합니다.

구현 코드

class Solution:
    def sign(self, word):
        value = 0
        for c in word:
            value = value | (1 << (ord(c) - 97))
        return value

    def solve(self, words):
        signature = [self.sign(x) for x in words]
        ans = 0
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if signature[i] & signature[j] == 0:
                    ans = max(ans, len(words[i]) + len(words[j]))
        return ans

ob = Solution()
words = ["abcd", "mno", "abdcmno", "amno"]
print(ob.solve(words))

입력

["abcd", "mno", "abdcmno", "amno"]

출력

7

시간 복잡도 분석

각 단어의 시그니처를 계산하는 데는 O(L)이 소요됩니다(L은 단어의 평균 길이). 이후 모든 단어 쌍을 비교하는 데는 O(n²)의 시간이 걸리며, 여기서 n은 단어의 개수입니다. 비트 연산 덕분에 각 쌍의 공통 문자 검사는 상수 시간(O(1))에 처리되므로, 문자별 비교 방식보다 훨씬 빠른 성능을 얻을 수 있습니다.