파이썬으로 문자열에서 큰 그룹의 시작·끝 위치 찾기

문제 설명

소문자로만 이루어진 문자열 S가 있다고 가정해 봅시다. 이 문자열은 같은 문자가 연속해서 나타나는 여러 개의 그룹으로 구성됩니다. 예를 들어 문자열 S가 "abbxxxxzyy"라면, "a", "bb", "xxxx", "z", "yy"라는 다섯 개의 그룹으로 나눌 수 있습니다.

이때 3개 이상의 문자를 포함하는 그룹을 '큰 그룹(large group)'이라고 정의합니다. 우리가 구해야 할 것은 문자열 내 모든 큰 그룹의 시작 인덱스와 끝 인덱스입니다.

예를 들어 입력이 "abcdddeeeeaabbbcd"라면, 결과는 [[3,5], [6,9], [12,14]]가 됩니다.

• [3, 5] → "ddd"
• [6, 9] → "eeee"
• [12, 14] → "bbb"

해결 접근 방법

이 문제는 파이썬의 itertools.groupby를 활용하면 간단하게 해결할 수 있습니다. 알고리즘의 흐름은 다음과 같습니다.

• 정답을 저장할 리스트 ans와 누적 인덱스 csum을 초기화합니다.
• groupby로 연속된 같은 문자들을 하나의 그룹으로 묶습니다.
• 각 그룹의 길이가 3 이상이면, [csum, csum + 그룹 길이 − 1]을 ans에 추가합니다.
• 그룹을 처리한 후에는 csum에 해당 그룹의 길이를 더해 다음 그룹의 시작 위치를 갱신합니다.
• 모든 그룹을 순회한 뒤 ans를 반환합니다.

구현 예제

from itertools import groupby

class Solution:
    def largeGroupPositions(self, S):
        ans = []
        csum = 0
        for a, b in groupby(S):
            grp = list(b)
            if len(grp) >= 3:
                ans.append([csum, csum + len(grp) - 1])
            csum += len(grp)
        return ans

ob = Solution()
print(ob.largeGroupPositions("abcdddeeeeaabbbcd"))

입력

"abcdddeeeeaabbbcd"

출력

[[3, 5], [6, 9], [12, 14]]

복잡도 분석

이 풀이는 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 그룹 정보를 저장하는 공간 복잡도 역시 O(n)입니다. groupby 덕분에 반복문 안에서 직접 문자를 비교하는 코드 없이도 깔끔하게 그룹을 나눌 수 있다는 점이 핵심입니다.