[리트코드] 15일차

228. Summary Ranges

오늘은 Inteval 이라는 주제의 문제들이다.

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


        int prev = nums[0];
        for (int i = 0; i < nums.length-1; i++){
            if(nums[i+1] - nums[i] != 1){
                if (nums[i] == prev){
                    answer.add(Integer.toString(nums[i]));
                }else{
                    answer.add(prev + "->"+nums[i]);
                }
                prev = nums[i+1];
            }
        }
        if (nums[nums.length-1] == prev){
            answer.add(Integer.toString(nums[nums.length-1]));
        }else{
            answer.add(prev + "->"+nums[nums.length-1]);
        }
        return answer;
    }
}

풀긴풀었으나.. 시간이 오래걸리고 중복되는 코드도 많다. 해결할 순 없을까?

다른 풀이들을 보니 딱히 크게 다른 로직은 아니었다. 이 코드보다 깔끔한 정도.

문제 의도에 맞게 풀긴 한 것 같다.

 

56. Merge Intervals

처음엔 별로 안 어렵겠지 하고 풀었는데, 반례가 많아져서 점점 잘 못 풀었다는 것을 확인해갔다.

딱히 정렬되어있는 배열이 아니었고, 그러다보니까 계속 오류가 났다.

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> answer= new ArrayList<>();
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int start = -1;
        int end = -1;

        for (int i = 0; i<intervals.length; i++){
            
            if ((end >= intervals[i][0])){
                if (start > intervals[i][0]){
                    start = intervals[i][0];
                }
                if (end < intervals[i][1]){
                    end = intervals[i][1];
                }
            }else{
                answer.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }

        answer.add(new int[]{start, end});
        return answer.subList(1, answer.size()).toArray(new int[0][]);
    }
}

정렬을 쓰다보니 10ms 가량 나오고, 이게 올바른 풀이가 아니라는 생각이 들었다. 근데 막상 풀이를 보니, 다들 이렇게 풀길래 이번에도 의도에 맞게 잘 풀었나보다. 조금 개선할 점이라면 이제 정렬을 했기 때문에 굳이 start 의 값을 min 값으로 설정하는 게 필요 없다 정도.

 

57. Insert Interval

위의 문제에서 별반 다르지 않은데 꽤나 어려웠다. 

사실 처음에 떠올랐던 방안은 주어진 배열에 넣고 정렬하고 위에 처럼 푸는 거였는데 오래걸릴 것 같아서 안했다.

그런데 풀이보니까 이렇게 푸네..

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> intervalList = new ArrayList<>(Arrays.asList(intervals));
        intervalList.add(newInterval);
        Collections.sort(intervalList, (a,b) -> Integer.compare(a[0], b[0]));

        List<int[]> res = new ArrayList<>();
        int[] current = intervalList.get(0);

        for (int i = 1; i <intervalList.size(); i++){
            int[] interval = intervalList.get(i);

            if (current[1] >= interval[0]){
                current[1] = Math.max(current[1], interval[1]);
            }else{
                res.add(current);
                current = interval;
            }
        }
        res.add(current);
        return res.toArray(new int[res.size()][]);
    }
}

밑에보니 내가 해보려고 했던 방법이 있길래 펼쳐봤다.

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
       int n = intervals.length;
        List<int[]> res = new ArrayList<>();

        int i = 0;
        while (i < n && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i]);
            i++;
        }

        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }

        res.add(newInterval);

        while (i < n) {
            res.add(intervals[i]);
            i++;
        }

        return res.toArray(new int[res.size()][]);
    }
}

코드가 깔끔했다. 나는 내가 다시 봐도 이해하기 힘들었는데 논리정연했다. 

관련있는 곳까지 간 다음 계속 계산하는 방식이었다. 나랑 다르게 newInterval 자체의 값을 변경하는 것이었다. 깔끔하다. 다음엔 이렇게 풀어야지.