LeetCode 228(Summary Ranges, Python)

1. 문제 링크

• Summary Ranges - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• 정렬된 정수 배열이 주어졌을 때, 연속된 범위를 요약하여 문자열의 리스트로 반환하는 것
• 예시) [0,1,2,4,5,7]이 주어지면, 이 배열을 연속된 범위로 요약하면 ["0->2","4->5","7"]

3. 처음 풀이

• two pointers 기법을 이용, start, end를 index=0 에서 출발시키고 start가 리스트의 끝에 도달할 때까지 whille문 반복한다.
• end의 수가 end+1의 수와 연속이면 end를 1 증가 시킴.
• 이때 start < end이면 연속한 수가 있다는 것이므로 start 수와 end 수를 화살표로 이어 result에 append
• 그렇지 않고 start = end 이면 연속한 수 없이 단일 수이므로 그냥 수를 reuslt에 append
• end를 1 증가시키고 start를 end와 일치시킨 후 반복문 다시 돌기.

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        start = end = 0
        result = []
        
        if len(nums) == 0:  # 만약 nums가 비어있으면 빈 리스트 반환
            return []
        if len(nums) == 1:  # 만약 nums에 하나의 요소만 있으면 해당 요소를 문자열로 변환하여 리스트로 반환
            return [str(nums[0])]
        
        while start < len(nums):  # nums의 모든 요소를 순회
            while end < len(nums) - 1 and nums[end] + 1 == nums[end + 1]:  # 연속된 숫자들을 찾는 루프
                end += 1
            if start < end:  # 연속된 숫자가 존재하는 경우
                result.append(str(nums[start]) + '->' + str(nums[end]))  # 시작과 끝을 화살표로 표현하여 리스트에 추가
            elif start == end:  # 연속된 숫자가 없는 경우
                result.append(str(nums[start]))  # 숫자 하나를 리스트에 추가
            end += 1
            start = end  # 다음 순회를 위해 start와 end를 업데이트
            
        return result  # 최종 결과 반환

4. 다른 풀이

• 리스트의 각 숫자 n이 연속이든 아니든 일단 [n, n]을 저장해두고
• 그 다음 수를 조회하여 n+1이면 [n, n]을 [n, n+1]로 업데이트하는 방식
• 마지막에는 문자열 formatting을 이용하여 [n, m]의 n, m이 같으면 n을, 다르면 n->m을 추가한다.

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        ranges = []  # 범위를 저장할 리스트 [시작, 끝] 형태로 저장하거나 [x, y] 형태로 저장
        for n in nums:  # 주어진 숫자들을 순회
            if ranges and ranges[-1][1] == n-1:  # 현재 숫자가 이전 범위의 끝 다음 숫자인 경우
                ranges[-1][1] = n  # 기존 범위의 끝을 업데이트
            else:
                ranges.append([n, n])  # 새로운 범위를 추가

        return [f'{x}->{y}' if x != y else f'{x}' for x, y in ranges]  # 결과를 문자열로 변환하여 반환

5. 배운 점

• 포인터를 두 개 두어 연속인지 따지면서 넣어도 되지만, 포인터를 하나 두고 일단 넣고 연속인지 따지며 수정할 수도 있다. 그리고 문자열 포맷팅은 아직 익숙하지 않은데 익숙해지면 꽤 편리할 듯.