228. Summary Ranges

문제 링크: https://leetcode.com/problems/summary-ranges/

정렬된 배열 nums를 받아서, the smallest sorted list of ranges that cover all the numbers in the array 를 반환하는 문제이다.

즉, 연속된 숫자들은 첫 숫자와 끝 숫자를 →로 잇는 range로 만들고, 그렇지 않은 숫자들은 그대로 list에 넣으면 된다.

우선, 첫 숫자인 start와 끝 숫자인 end를 →로 이어 range String을 반환하는 getRange()라는 메소드를 만들었다.

public String getRange(int start, int end) {
        StringBuilder sb = new StringBuilder();
        sb.append(start);
        if(start != end) sb.append("->").append(end);
        return sb.toString();
    }

String을 append하기 위해서는 StringBuilder를 사용했다.

StringBuilder

String은 immutable 하기 때문에, String 객체는 한번 생성되면 할당된 메모리 공간이 변하지 않는다.
"+" 연산자 또는 concat 메서드를 통해 기존에 생성된 String 클래스 객체 문자열에 다른 문자열을 붙여도 기존 문자열에 새로운 문자열을 붙이는 것이 아니라, 새로운 String 객체를 만든 후, 새 String 객체에 연결된 문자열을 저장하고, 그 객체를 참조하도록 한다. (즉, String 클래스 객체는 Heap 메모리 영역(가비지 컬렉션이 동작하는 영역)에 생성되며 한번 생성된 객체의 내부 내용을 변화시킬 수 없다.)

String 객체는 이러한 이유로 문자열 연산이 많은 경우, 그 성능이 좋지 않다.
이에 반해 StringBuilder는 String처럼 새로운 객체를 만들지 않고도 문자열을 수정할 수 있기 때문에 mutable하며 단일쓰레드에서의 성능은 StringBuffer 보다 뛰어나다.
따라서 range String을 만드는데에 StringBuilder를 사용했다.

이때, 첫 숫자인 start와 끝 숫자인 end가 동일한 경우 숫자 하나만 range에 넣도록 조건을 추가했다.

다음으로 input 배열의 원소를 하나씩 순회하며 연속한 두 원소를 비교해, 두 숫자가 연속하지 않는 경우 subrange를 끊고 getRange()로 range String을 만들어 반환할 list에 삽입했다. 연속하지 않은 두번째 숫자는 start 변수에 넣어 다음의 subRange를 시작하도록 했다.

이렇게 문제를 풀면 배열의 마지막 원소 하나가 list에 들어가지 못 한 채로 남게 된다.
이를 그대로 end변수에 넣어 getRange()함수를 호출하면, 배열의 마지막 원소가 이 전 subRange에 이어질 경우 subRange에 추가 되고, 그렇지 않을 경우 단독 subRange로 할당된다.

Solution

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> summaryOfTheRange = new ArrayList<String>();
        if(nums.length == 0) return summaryOfTheRange;
        
        String subRange="";
        int start=nums[0];
        for(int i=1;i<nums.length;i++) {
            if(nums[i-1]+1 != nums[i]) { 
                subRange = getRange(start, nums[i-1]);
                summaryOfTheRange.add(subRange);
                start = nums[i];
            }
        }
        subRange = getRange(start, nums[nums.length-1]);
        summaryOfTheRange.add(subRange);
        return summaryOfTheRange;
    }
    
    public String getRange(int start, int end) {
        StringBuilder sb = new StringBuilder();
        sb.append(start);
        if(start != end) sb.append("->").append(end);
        return sb.toString();
    }
}