Python으로 같은 첫 글자를 가진 가장 긴 연속 부분 리스트의 길이 찾기

문제 개요

소문자 알파벳 문자열로 이루어진 words 리스트가 주어졌다고 가정해 봅시다. 이때, 각 단어의 첫 글자가 모두 동일한 가장 긴 연속 부분 리스트(contiguous sublist)의 길이를 구하는 것이 목표입니다.

예를 들어 입력이 다음과 같다고 해보겠습니다.

words = ["she", "sells", "seashells", "on", "the", "sea", "shore"]

이 경우 정답은 3입니다. 가장 긴 연속 부분 리스트는 ["she", "sells", "seashells"]이며, 세 단어 모두 첫 글자가 's'로 같기 때문입니다.

해결 접근 방식

이 문제는 리스트를 한 번만 순회하면서 현재 연속 구간의 길이와 최댓값을 추적하면 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

현재 연속 구간의 길이를 저장할 카운터(cnt)와 전체 최댓값(maxcnt)을 준비합니다.
바로 앞 단어의 첫 글자(prev_char)와 현재 단어의 첫 글자를 비교합니다.
첫 글자가 같으면 카운터를 증가시키고, 다르면 새로운 구간이 시작된 것이므로 카운터를 1로 초기화합니다.
매 단계마다 최댓값을 갱신한 뒤, 마지막에 최댓값을 반환합니다.

알고리즘 단계

cnt = 1, maxcnt = 0, prev_char = ""로 초기화합니다.
리스트의 각 단어에 대해 다음을 수행합니다.
- prev_char가 비어 있다면, 해당 단어의 첫 글자를 prev_char에 저장합니다.
- prev_char가 현재 단어의 첫 글자와 같다면, cnt를 1 증가시킵니다.
- 그렇지 않다면, prev_char를 새로운 첫 글자로 갱신하고 cnt를 1로 초기화합니다.
매 반복마다 maxcnt = max(maxcnt, cnt)로 최댓값을 갱신합니다.
순회가 끝나면 maxcnt를 반환합니다.

Python 구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

def solve(words):
    cnt = 1
    maxcnt = 0
    prev_char = ""
    for word in words:
        if prev_char == "":
            prev_char = word[0]
        elif prev_char == word[0]:
            cnt += 1
        else:
            prev_char = word[0]
            cnt = 1
        maxcnt = max(maxcnt, cnt)
    return maxcnt

words = ["she", "sells", "seashells", "on", "the", "sea", "shore"]
print(solve(words))

입력

["she", "sells", "seashells", "on", "the", "sea", "shore"]

출력

복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하기 때문에 시간 복잡도는 O(n)입니다(n은 단어의 개수). 추가로 사용하는 변수는 상수 개수뿐이므로 공간 복잡도 역시 O(1)로 매우 효율적입니다.