문제 15: 최장 공통 접두사

Source: Dev.to

문제

목표는 문자열 리스트에서 가장 긴 공통 접두사를 찾는 함수를 작성하는 것입니다.

• 접두사는 문자열의 시작 부분에 나타나는 부분 문자열입니다.
• 함수는 리스트에 있는 모든 단어가 시작하는 가장 긴 공통 문자열을 반환해야 합니다.
• 공통 접두사가 없으면 빈 문자열 ""을 반환해야 합니다.

예시

longest_common_prefix(['flower', 'flow', 'flight'])   # → 'fl'
longest_common_prefix(['dog', 'racecar', 'car'])      # → ''
longest_common_prefix(['interspecies', 'interstellar'])  # → 'inters'

해결책

def longest_common_prefix(strings):
    """
    Finds the longest common prefix among a list of strings.
    """
    # Check for empty input
    if not strings:
        return ""

    # Start with the first string as the initial prefix
    prefix = strings[0]

    # Compare with each subsequent string
    for s in strings[1:]:
        # Shorten the prefix until it matches the start of the current string
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            # If the prefix becomes empty, there is no common prefix
            if prefix == "":
                return ""

    return prefix

# Test cases
print(longest_common_prefix(['flower', 'flow', 'flight']))      # 'fl'
print(longest_common_prefix(['dog', 'racecar', 'car']))         # ''
print(longest_common_prefix(['interspecies', 'interstellar']))  # 'inters'

코드 분석

함수 정의

def longest_common_prefix(strings):

리스트 형태의 문자열을 매개변수로 받는 함수를 정의합니다.

빈 입력 검사

if not strings:
    return ""

입력 리스트가 비어 있을 경우 빈 문자열을 반환합니다.

초기 접두사

prefix = strings[0]

첫 번째 문자열 전체를 가장 긴 공통 접두사로 가정합니다.

남은 문자열 순회

for s in strings[1:]:

첫 번째 문자열을 제외한 나머지 문자열을 차례로 검사합니다.

접두사 축소

while not s.startswith(prefix):
    prefix = prefix[:-1]
    if prefix == "":
        return ""

현재 문자열이 prefix로 시작하지 않으면 prefix의 마지막 문자를 하나씩 제거합니다.
prefix가 빈 문자열이 되면 공통 접두사가 없다는 의미이므로 바로 반환합니다.

결과 반환

return prefix

모든 문자열을 검사한 뒤 남은 prefix가 가장 긴 공통 접두사가 됩니다.

예시 진행

예시 1: ['flower', 'flow', 'flight']

1. 초기화: prefix = 'flower'
2. ‘flow’와 비교:
   • 'flow'가 'flower'로 시작하지 않음 → prefix = 'flowe'
   • 여전히 불일치 → prefix = 'flow' (이제 일치)
3. ‘flight’와 비교:
   • 'flight'가 'flow'로 시작하지 않음 → prefix = 'flo'
   • 여전히 불일치 → prefix = 'fl' (이제 일치)
4. 결과: 'fl'

예시 2: ['dog', 'racecar', 'car']

1. 초기화: prefix = 'dog'
2. ‘racecar’와 비교:
   • 불일치 → prefix = 'do' → 불일치 → prefix = 'd' → 불일치 → prefix = ''
3. 결과: '' (공통 접두사 없음)

주요 최적화

• 수평 매칭: 첫 문자열을 최대 가능한 접두사로 시작하고, 불일치가 발생할 때만 축소합니다. 이렇게 하면 모든 문자열을 문자 단위로 일일이 비교할 필요가 없습니다.
• 조기 종료: 접두사가 빈 문자열이 되면 즉시 알고리즘을 멈추어 불필요한 비교를 피합니다.

이 접근법은 간단하고 가독성이 좋으며 일반적인 사용 사례에 효율적입니다. 즐거운 코딩 되세요!