[파이썬] 리트코드 830. Positions of Large Groups 풀이

https://leetcode.com/problems/positions-of-large-groups/

Positions of Large Groups - LeetCode

abbxxxxzzy와 같이 문자열이 주어졌을 때, 3개 이상 연속된 문자가 나왔을 때의 시작과 끝 인덱스를 찾아내는 문제다.

처음에는 set을 이용해서 존재하는 문자를 찾아낸 뒤, 각각에 대해 count를 사용해서 3개가 넘을 경우 탐색하는 방식으로 풀었는데

3개 이상 존재하지만 3개 이상 연속되지 않는 경우가 존재할 수 있기 때문에 오답이 된다.

 

그래서, 

1. 앞에서부터 포인터를 이동시키면서 조회 

2. 시작 인덱스 저장

3. 앞의 문자와 뒤의 문자가 달라진 경우 -> 연속이 끝났다는 의미

4. 만약 이 인덱스와 시작 인덱스 사이의 문자 개수가 3 이상이라면 끝 인덱스로 저장하여 리스트에 append

와 같이 풀었다.

 

이런 문제는 굳이 창의적인 방법을 찾기보다는,

사람의 사고과정과 비슷하게 풀어내면 되는 것 같다. 

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        answer = [] 
        i = 0 # 그룹의 시작 
        for j in range(len(s)): 
            if j == len(s) -1  or s[j] != s[j+1]:
                if j-i+1 >= 3:
                    answer.append([i,j])
                i = j+1
        return answer