[Algorithm] Dart로 풀어보는 Summary Ranges 요약 범위

You are given a sorted unique integer array nums.
A range [a,b] is the set of all integers from a to b (inclusive).
Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:
- "a->b" if a != b
- "a" if a == b

Example 1:
Input: nums = [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: The ranges are: [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7"

Example 2:
Input: nums = [0,2,3,4,6,8,9] Output: ["0","2->4","6","8->9"] Explanation: The ranges are: [0,0] --> "0" [2,4] --> "2->4" [6,6] --> "6" [8,9] --> "8->9"

Constraints:
- 0 <= nums.length <= 20
- - 2(31승) <= nums[i] <= 2(31승) - 1
- All the values of nums are unique.
- nums is sorted in ascending order.

 

정렬된 고유한 정수 배열 nums가 주어졌을 때, 연속된 숫자들을 하나의 범위로 묶어 문자열 형태로 반환하세요. 각 범위는 "a->b"의 형식이며, 숫자가 하나만 포함될 경우 해당 숫자 "a"를 반환합니다.

 

나의 접근 방식

정렬된 연속된 숫자들을 비교해야 합니다. 그래서 반복문을 돌리면서 이전 값 + 1 과 현재 값 혹은 현재 값과 이후 값 - 1 비교를 해야겠다고 생각했습니다. 기본 알고리즘은 연속되지 않은 값이 발견될 때 "0" 혹은 "2->4" 와 같은 처리를 하는 것이었습니다.

 

리스트의 요소들이 연속되지 않은 숫자가 나올때(nums[i-1] + 1 != nums[i]) 반환해야 하는 리스트에 담아줘야하는데, 연속된 숫자를 그룹핑하기 위해서 count 라는 변수를 두고 얼마나 연속되었는지를 세도록 했습니다. 그룹핑을 하려는 숫자가 연속된 숫자가 아니면 홀로 묶어버리고 연속된 숫자라면 count 값이 계속 증가하고 연속되지 않은 숫자가 다시 등장하면 기존에 연속된 숫자들로 "2->4"와 같은 작업을 해줄 수 있습니다.

List<String> summaryRanges(List<int> nums) {
  if (nums.isEmpty) return [];
  if (nums.length == 1) return [nums[0].toString()];

  List<String> list = [];
  String next = '->';
  String start = nums[0].toString();
  int count = 1;

  for (int i = 1; i < nums.length; i++) {
    if (nums[i - 1] + 1 != nums[i]) {
      if (count == 1) {
        list.add(start);
      } else {
        list.add(start + next + nums[i - 1].toString());
      }
      start = nums[i].toString();
      count = 1;
    } else {
      count++;
    }
  }

  if (count > 1) {
    list.add(start + next + nums.last.toString());
  } else {
    list.add(start);
  }

  return list;
}

 

몇 가지의 알고리즘 문제들을 풀다보니 리스트(배열)와 관련된 작업을 할때 첫번째 값을 String start 라는 변수에 보관하고 값을 비교 및 처리하는 작업을 할 수 있음이 자연스럽게 떠올랐습니다.

 

이 알고리즘의 핵심은 어떻게 연속된 숫자를 파악할 수 있는지와 그리고 연속되지 않는 지점에서 어떤 작업이 이루어져야 함이었습니다. 아직도 알고리즘에 관해서는 초보자 레벨이고 초보자 레벨정도라도 감을 잊지 않도록 노력해야겠습니다.