리트코드 - 228. Summary Ranges

리트코드 - 228. Summary Ranges

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

 

문제 설명

주어진 것은 정렬된 고유한 정수 배열 nums입니다.

범위 [a, b]는 a부터 b까지의 모든 정수 집합입니다(a,b포함).

배열 내의 모든 숫자를 정확히 포함하는 가장 작은 정렬된 범위 목록을 반환하십시오. 즉, nums의 각 요소가 정확히 하나의 범위에 포함되며, 하나의 범위에 속하지만 nums에는 없는 정수 x가 없어야 합니다.

목록 내의 각 범위 [a, b]는 다음과 같이 출력되어야 합니다:

• "a->b" if a != b
• "a" if a == b

 

의사코드

list = new ArrayList if (nums.length == 0)     return list int start = nums[0] int end = start sb = new StringBuilder 반목문 시작 ( nums배열의 i=1부터 +1씩 순회)     if (nums[i] == end + 1)         end = nums[i]     else         sb의 길이를 0으로 설정         if (start == end)             sb에 start 추가         else             sb에 start, ->, end 추가         list에 sb 추가         start = nums[i]         end = start 반복문 종료 sb의 길이를 0으로 설정 if (start == end)     sb에 start 추가 else     sb에 start, ->, end 추가 list에 sb 추가 list 리턴

 

풀이코드

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        if (nums.length == 0) {
            return list;
        }

        int start = nums[0];
        int end = start;
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < nums.length; i++) { 
            if (nums[i] == end + 1) {
                end = nums[i];
            } else {
                sb.setLength(0); 
                if (start == end) {
                    sb.append(start);
                } else {
                    sb.append(start).append("->").append(end);
                }
                list.add(sb.toString());
                start = nums[i];
                end = start;
            }
        }

        sb.setLength(0); 
        if (start == end) {
            sb.append(start);
        } else {
            sb.append(start).append("->").append(end);
        }
        list.add(sb.toString());

        return list;
    }
}

코드설명

start와 end 초기값을 배열의 처음값으로 설정해주고, nums배열을 순회한다.

 

처음값은 설정했으므로 i=1부터 시작하는데, 배열의 값이 start의 +1 이 맞다면 end값을 갱신해준다.

만약 +1이 아닌 경우 정수배열이 끝난 것이므로 list에다가 값을 넣어주어야 한다.

문제 조건에 따라 값이 하나인 경우와 여러개인 경우를 나누어주어야 하는데 start와 end가 같다면 StringBuilder를 이용해서 그냥 start 값만 넣어주면 되고, 같지 않으면 start와 end값 사이에 "->" 를 넣어주면 된다.

 

이렇게 만든 sb값을 list에 넣기위해 .toString()을 해주고, 다시 start값과 end값을 현재 배열의 값으로 설정해주면 된다.

이렇게 반복하면 정수배열이 list에 담기는데, 배열의 끝에 도달했을때 마지막 정수배열은 담지 못한다.

따라서 마지막 정수배열에 대한 조건도 확인하여 list에 추가하면 끝난다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

처음에는 최대한 빨리 푸는 방법을 고려해봤다.

 

초기코드

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        if (nums.length == 0) {
            return list;
        }
        if (nums.length == 1) {
            list.add(nums[0] + "");
            return list;
        }
        int standard = nums[0];
        int count = 1;

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

            if (i == nums.length - 1) {
                if (count == 1) {
                    list.add(nums[i] + "");
                } else {
                    list.add(standard + "->" + nums[i]);
                }
            }
        }

        return list;
    }
}

가장 먼저 드는 생각은 count를 이용해서 count가 1이면 그냥 값을 list에 더해주고, 1보다 크다면 화살표를 추가하는 방법을 생각해봤다.

 

Runtime - 6ms

Memory - 40.8MB

 

리팩토링 1차

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        if (nums.length == 0) {
            return list;
        }

        int start = nums[0];
        int end = nums[0];

        for (int i = 1; i < nums.length; i++) { 
            if (nums[i] == end + 1) {
                end = nums[i];
            } else {
                if (start == end) {
                    list.add(String.valueOf(start));
                } else {
                    list.add(start + "->" + end);
                }
                start = nums[i];
                end = nums[i];
            }
        }

        if (start == end) {
            list.add(String.valueOf(start));
        } else {
            list.add(start + "->" + end);
        }

        return list;
    }
}

문제를 다시 보니 문제에서 약간 힌트가 있었다.

이런식으로 설명이되어 있어서 start와 end 값을 두고 확인하는게 더 나을것 같다는 생각이 들었다.

String.valueOf도 써봤는데 그냥 "" 공백을 더하는 것과 큰 런타임 차이는 없었다.

 

리팩토링 2차

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        if (nums.length == 0) {
            return list;
        }

        int start = nums[0];
        int end = start;

        for (int i = 1; i < nums.length; i++) { 
            StringBuilder sb = new StringBuilder();
            if (nums[i] == end + 1) {
                end = nums[i];
            } else {
                if (start == end) {
                    sb.append(start+ "");
                    list.add(sb.toString());
                } else {
                    sb.append(start);
                    sb.append("->");
                    sb.append(end);
                    list.add(sb.toString());
                }
                start = nums[i];
                end = start;
            }
        }

        if (start == end) {
            list.add(start + "");
        } else {
            list.add(start + "->" + end);
        }

        return list;
    }
}

StringBuilder를 이용해서 값을 더하는 방법을 택했다.

위 코드에서는 반복문 시작에 sb를 초기화 했는데, sb값 자체를 초기화하는 방법도 있어서 적용한 것이 풀이에서의 코드이다.

 

런타임이 0ms으로 100%를 달성했고, 메모리도 가장 적게 먹는 코드를 작성할 수 있었다.

 

정리

String을 더할때에는 StringBuilder를 사용할 것.