[Java] leetcode 352. Data Stream as Disjoint Intervals

문제

https://leetcode.com/problems/data-stream-as-disjoint-intervals/description/

Data Stream as Disjoint Intervals - LeetCode

주어진 조건에 맞추어 메소드를 구현하는 문제 

알아야 할 개념

• 이진 탐색 

풀이

풀이는 다음과 같다. 

SummaryRanges()  

1. 리스트 전역변수 arr 를 초기화 한다. 

void addNum(int value) 

1. 이진 검색을 구현해서, arr 리스트를 탐색한다. arr.contains(value) 일 경우 -1 을 리턴 (중복 제거 )
2. 그 이외에는 삽입할 위치를 리턴한다. 

int[][] getIntervals() 

1. arr 리스트를 탐색을 하여 prev 보다 1 증가할 경우에만 업데이트를 해준다. 
2. 그 이외에는 새로운 리스트를 추가한다. 

 

 

코드

자바

class SummaryRanges {

    ArrayList<Integer> arr;
    public SummaryRanges() {
        arr = new ArrayList<>();
    }
    
    public void addNum(int value) {
        int i = bnS(arr, value);
        if(i == -1)return;
        if(arr.size() <= i)arr.add(value);
        else{
            arr.add(i,value);
        }
    }
    public int bnS(List<Integer> l, int v){
        int left = 0;
        int right = l.size()-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(l.get(mid) == v)return -1;
            else if(l.get(mid) < v)left = mid+1;
            else right = mid-1;
        }
        //System.out.println(left);
        return left;
    }
    
    public int[][] getIntervals() {
        ArrayList<ArrayList<Integer>> temp = new ArrayList<>();
        int prev =-1;
        int cnt = 0;
        //System.out.println(arr);
        for(int i = 0 ;i < arr.size() ;i++){
            if(i > 0 && arr.get(i) == arr.get(i-1))continue;
               if(prev ==-1){
                   prev = arr.get(i);
                   temp.add(new ArrayList<Integer>());
                   temp.get(cnt).add(prev);
                   temp.get(cnt).add(prev);
               }else{
                   if(arr.get(i)-1 == prev){
                       temp.get(cnt).set(1,arr.get(i));
                       prev = arr.get(i);
                   }else {
                        cnt++;
                        prev = arr.get(i);
                        temp.add(new ArrayList<Integer>());
                        temp.get(cnt).add(prev);
                        temp.get(cnt).add(prev);
                   }
               }
        }
        int[][] ret = new int[temp.size()][2];
        for(int i =0 ;i < temp.size() ;i++){
            ret[i] = temp.get(i).stream().mapToInt(x->x).toArray();
        }
        return ret;
    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(value);
 * int[][] param_2 = obj.getIntervals();
 */