[Dart] 228. Summary Ranges

1. 문제

 

https://leetcode.com/problems/summary-ranges/description/?envType=study-plan-v2&envId=top-interview-150

 

 

 

2. 요구사항

1) 정렬된 정수 배열 nums가 주어진다.

2) 연속된 숫자들을 하나의 범위로 묶어 문자열 형태로 반환한다.

3) 출력은 오름차순으로 정렬된 문자열 리스트이다.

4) 빈 배열일 경우, 빈 리스트 []를 반환한다.

 

 

 

3. 핵심 아이디어

1) 배열을 순회하며 연속적인 숫자인지 확인

배열을 순회하며 연속적인 숫자를 찾아야 한다.

 

만약 연속적이지 않은 숫자를 만나거나 배열의 마지막 숫자에 도달하면,

지금까지 추적해온 범위의 시작 숫자부터 현재 숫자까지를 문자열로 만들어 결과 리스트에 저장한다.

 

새로운 연속 범위를 시작하기 위해 start 값을 다음 숫자로 갱신한다.

 

 

 

2) 코드

class Solution {
  List<String> summaryRanges(List<int> nums) {
    // 결과를 저장할 리스트
    List<String> result = [];
    int n = nums.length;

    // 배열이 비어있으면 빈 리스트 반환
    if (n == 0) return result;

    // 첫 번째 숫자를 범위의 시작점으로 설정
    int start = nums[0];

    for (int i = 0; i < n; i++) {
      // 마지막 원소이거나, 현재 숫자와 다음 숫자가 연속되지 않을 때
      if (i == n - 1 || nums[i] + 1 != nums[i + 1]) {
        // 범위가 한 숫자일 경우
        if (start == nums[i]) {
          result.add(start.toString());
        } else {
          // 범위가 여러 숫자일 경우
          result.add("$start->${nums[i]}");
        }

        // 다음 범위의 시작점을 설정
        if (i != n - 1) {
          start = nums[i + 1];
        }
      }
    }

    return result;
  }
}

 

- 시간 복잡도 : O(n)

- 공간 복잡도 : O(1)