[반복문] LeetCode 228번 문제 학습

 

문제 설명

Summary Ranges는 정수 배열 nums에서 연속된 숫자 구간을 문자열 배열로 표현하는 문제임. 각 구간은 시작과 끝 숫자를 "시작->끝" 형식으로 나타내고, 숫자 하나면 그냥 문자열로 추가. 예를 들어, nums = [0,1,2,4,5,7]이면 ["0->2","4->5","7"] 리턴. nums = [0,2,3,4,6,8,9]면 ["0","2->4","6","8->9"]. 배열은 오름차순이고 중복 없음.

 

푼 과정

배열 순회하면서 연속 구간 찾음. start로 구간 시작 인덱스 관리하고, i로 현재 인덱스 이동. i가 마지막이거나 nums[i]+1이 다음 숫자와 다르면 구간 끝남.

start == i면 숫자 하나라 nums[start]를 문자열로 추가. 다르면 nums[start]->nums[i] 형식으로 추가.

구간 끝나면 start를 i+1로 갱신. 빈 배열은 빈 문자열 배열 리턴

맨 마지막 요소는 조건으로 처리돼서 자연스럽게 append됨.

---

알고리즘 분석

단일 순회 썼음. 배열 한 번 돌면서 구간 체크하고 문자열로 변환. 시간 O(n), n은 배열 길이. 문자열 변환(strconv.Itoa)은 각 구간마다 O(1) 정도로 작음. 공간 O(1), 출력 배열 제외하면 상수 메모리만 씀. 결과 배열은 O(n) 최악(모두 단일 숫자일 때). 다른 방법으론 투 포인터나 재귀 가능하지만, 단일 순회로 충분히 효율적.

func summaryRanges(nums []int) []string {
	if len(nums) == 0 {
		return []string{}
	}

	result := []string{}
	start := 0 // 구간 시작 인덱스

	for i := 0; i < len(nums); i++ {
		// 마지막이거나 다음 숫자가 연속이 아니면 구간 종료
		if i == len(nums)-1 || nums[i]+1 != nums[i+1] {
			if start == i {
				// 숫자 하나만 있는 구간
				result = append(result, strconv.Itoa(nums[start]))
			} else {
				// 연속된 숫자 구간
				result = append(result, strconv.Itoa(nums[start])+"->"+strconv.Itoa(nums[i]))
			}
			start = i + 1 // 새로운 구간 시작
		}
	}

	return result
}