파이썬으로 같은 첫 글자를 공유하는 최장 연속 단어 구간 찾기

문제 개요

소문자로만 이루어진 단어 목록이 주어졌을 때, 모든 단어가 같은 첫 글자를 공유하는 가장 긴 연속 부분 리스트의 길이를 찾아야 합니다.

예를 들어 입력이 ["she", "sells", "seashells", "on", "the", "seashore"]라면 출력은 3이 됩니다. "she", "sells", "seashells" 세 단어가 서로 인접해 있고, 첫 글자가 모두 's'로 동일하기 때문입니다.

풀이 접근 방법

이 문제는 리스트를 한 번만 순회하면서 현재 구간의 첫 글자와 구간 길이를 함께 추적하는 방식으로 해결할 수 있습니다. 새로운 첫 글자를 가진 단어가 등장하면 지금까지 누적된 구간 길이를 최댓값과 비교해 갱신하고, 카운터를 새로 초기화하면 됩니다.

• maxlength(최대 길이)를 0으로 초기화합니다.
• curr_letter(현재 글자)는 None, curr_length(현재 길이)는 0으로 초기화합니다.
• words의 각 단어에 대해 다음을 반복합니다.
  • curr_letter가 None이거나 curr_letter가 word[0]과 다른 경우
    • maxlength를 maxlength와 curr_length 중 더 큰 값으로 갱신합니다.
    • curr_letter를 word[0]으로, curr_length를 1로 설정합니다.
  • 그 외의 경우
    • curr_length를 1 증가시킵니다.
• 마지막으로 maxlength와 curr_length 중 더 큰 값을 반환합니다.

구현 예제

아래 예제 코드를 통해 실제 동작 과정을 더 쉽게 이해할 수 있습니다.

class Solution:
   def solve(self, words):
      maxlength = 0
      curr_letter, curr_length = None, 0
      for word in words:
         if not curr_letter or curr_letter != word[0]:
            maxlength = max(maxlength, curr_length)
            curr_letter, curr_length = word[0], 1
         else:
            curr_length += 1
      return max(maxlength, curr_length)
ob = Solution()
words = ["she", "sells", "seashells", "on", "the", "seashore"]
print(ob.solve(words))

입력

["she", "sells", "seashells", "on", "the", "seashore"]

출력

3

시간 복잡도 분석

모든 단어를 정확히 한 번씩만 확인하므로 시간 복잡도는 O(n)입니다. 또한 추가로 사용하는 변수가 상수 개수에 불과하므로 공간 복잡도 역시 O(1)로, 매우 효율적인 선형 탐색 알고리즘입니다.