[LeetCode] 228. Summary Ranges

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

Summary Ranges - LeetCode

문제 유형 : 투 포인터 / 배열

문제 난이도 : Easy

 

문제

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

요소가 겹치지 않는 오름차순정렬된 정수배열 nums가 있다.

범위 [a,b]는 a에서부터 b까지의 집합이다.

배열의 모든 요소를 담는 오름차순 정렬된 범위 리스트를 반환하라.

 

 

풀이

정답을 모으는 문자열 배열을 만든다.

left포인터를 생성한다.

left가 n(주어진 배열의 길이)보다 작은 동안:

    right을 생성해서 처음에는 left와 같게 한다.

    right이 범위를 넘지 않고, 다음 수와 연속적으로 커지는 경우, right의 크기를 1씩 늘린다.

 

    늘릴 수 있는만큼 right을 키우고, 

    left와 right이 같다면 배열에 nums[left]를 문자열로 정답 배열에 추가해준다.

    다르다면 "nums[left] -> nums[right]"문자열을 만들어서 정답 배열에 추가시킨다.

 

다 끝나면, 문자열 배열에 올바른 범위 리스트가 생성되어있다.

 

코드

형변환에 주의해서 코드를 작성해야한다.

C++

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        const int n = nums.size();
        int left = 0;
        vector<string> answer;
        while(left < n) {
            int right = left;
            if(right < n-1 && nums[right]+1 == nums[right+1]) {
                while(right < n-1 && nums[right]+1 == nums[right+1]) {
                    right++;
                }
            }
            

            if(left == right) {
                answer.push_back(to_string(nums[left]));
            } else {
                answer.push_back(to_string(nums[left]) + "->" + to_string(nums[right]));

            }

            left = right+1;
        }

        return answer;
    }
};

 

Python3

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        n = len(nums)
        answer = []
        left = 0

        while left < n:
            right = left
            if right < n-1 and nums[right]+1 == nums[right+1]:
                while right < n-1 and nums[right]+1 == nums[right+1]:
                    right += 1

            if left == right:
                answer.append(str(nums[left]))
            else:
                answer.append(str(nums[left]) + "->" + str(nums[right]))

            left = right+1

        return answer

 

Java

class Solution {
    public List<String> summaryRanges(int[] nums) {
        final int n = nums.length;
        ArrayList<String> answer = new ArrayList<>();
        int left = 0;

        while(left < n) {
            int right = left;

            if(right < n-1 && nums[right] + 1 == nums[right+1]) {
                while(right < n-1 && nums[right] + 1 == nums[right+1]) {
                    right++;
                }
            }

            if(left == right) {
                answer.add(Integer.toString(nums[left]));
            } else {
                answer.add(Integer.toString(nums[left]) + "->" + Integer.toString(nums[right]));
            }

            left = ++right;
        }

        return answer;
    }
}