[Leetcode] 228. Summary Ranges - JS

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

 

1. 문제 분석

문제분석
--------------------
- 정렬된 유일한 정수로 구성된 배열 nums가 주어진다.
- range [a, b]는 a, b 사이의 모든 정수 집합이다.
- 정확히 배열안의 모든 숫자를 포함하는 가장 작은 리스트 범위를 반환하라.
- x가 범위에는 포함되지만 nums에 존재하지 않을 수는 없다.
- 목록의 각 범위 [a,b]는 다음과 같이 출력되어야 합니다.
    - a != b인 경우 "a->b"
    - a == b인 경우 "a"

제한조건
--------------------
- 0 <= nums.length <= 20
- -2^31 <= nums[i] <= 2^31 - 1
- nums의 모든 값은 유일한 값이다.
- nums는 오름차순 정렬되어 있다.

 

2. 접근 방법

접근방법
--------------------
nums 순회하면서 인덱스 값과 다음 인덱스 값이 1만큼 차이나는지 반복 비교
    - 1만큼 차이나면 인덱스 이동
    - 연속되지 않으면
        - 처음 인덱스의 요소와 이동한 인덱스의 요소가 다르면 'a->b'
        - 같으면 'a'

 

 

3. 코드

var summaryRanges = function(nums) {    
    const res = [];
    
    // nums 배열을 순회
    for (let i = 0; i < nums.length; i++) {
        let start = nums[i];
        
        // 다음 숫자가 연속적인 경우 찾기
        while (nums[i + 1] === nums[i] + 1) {
            i++;
        }
        
        // 범위가 형성되었는지 확인
        if (start !== nums[i]) {
            res.push(`${start}->${nums[i]}`);
        } else {
            res.push(`${start}`);
        }
    }
    
    return res;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

[Leetcode] 128. Longest Consecutive Sequence - JS 해당 문제와 비슷하게 접근했었다.

Set 자료구조로 연속되는 숫자가 있는지 확인하여 length를 추가해주면서 범위를 설정해주었는데,

이미 문제에선 유일한 값이라고 했으므로 굳이 Set 자료구조를 사용할 필요가 없어서

Set 자료구조 사용하지 않는 방법이 있는지 GPT에게 물어봤다.

 

Set 사용하지 않고 nums 에 접근하는 index값을 통해 연속적인 값이 있으면 index를 한칸씩 이동시키면서

처음 인덱스로 참조한 요소와 이동한 인덱스로 참조한 요소가 같은지 다른지 비교하여 결과를 도출했다.

문제에서 오름차순으로 정렬되고, 유일한 요소로 구성되어 있다고 하였으므로,

Set 자료구조 사용하지 않고 index를 통해 다음 요소가 연속적인 값인지 알 수 있었다.

 

문제에서 주어진 조건에 따라 접근 방법을 달리 해야한다는 것을 느낄 수 있는 문제였던 것 같다.