[Java] LeetCode 352. Data Stream as Disjoint Intervals

[Java] LeetCode 352. Data Stream as Disjoint Intervals

 

문   제 : 

3가지 함수를 작성해야한다.

1. 생성자 함수

2. addNum(int value) -> 숫자를 추가하는 함수

3. getIntevals() -> 추가된 숫자들을 기반으로 인터벌을 출력하는 함수

 

{ 0 <= value <= 10^4 }

 

 

Example )

Input : 
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", 
"addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]

Output : 
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, 
[[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, 
[[1, 3], [6, 7]]]

Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]

 

---

접   근 : 

ArrayList에 각 숫자들을 추가하고 출력할 땐 한 숫자씩 접근하여 해당 숫자가 연결된 수자가 있는지 없는지 확인하고 리스트를 만들어 결과 리스트에 추가한다.

---

해   결 : 

생성자 함수 :

value를 저장할 ArrayList 초기화

 

addNum 함수 : 

숫자가 중복되지 않게 contains 메소드를 이용해 검사한 후 없는 숫자이면 ArrayList에 추가

 

getIntervals 함수 :

    변 수 :

res : 결과 배열을 저장할 List를 원소로 갖는 ArrayList

result : 리턴 될 결과 2차원 배열

temp : res에 들어갈 원소 List

before : 이전에 나왔던 숫자

 

---

생성자 함수 작성

 

 

public SummaryRanges() {
    arr = new ArrayList<>();
}

 

 

---

 

addNum 함수 작성

 

public void addNum(int value) {
    if(!arr.contains(value)) arr.add(value);
}

 

---

 

getIntervals() 함수 작성

 

public int[][] getIntervals() {
    ArrayList<List<Integer>> res = new ArrayList<>();
    int[][] result;
    List<Integer> temp = new ArrayList<>();
    int before;

    Collections.sort(arr);


    if(arr == null) return null;

    // 첫 초기화
    before = arr.get(0);
    temp.add(arr.get(0));

    for(int i=0; i<arr.size()-1; i++){
        if(arr.get(i+1) == before+1){ // 다음 숫자가 연결된 숫자라면
            before++;
        }
        else if(arr.get(i+1) != before+1){ // 다음 숫자가 연결된 숫자가 아니라면
            temp.add(before); // 끝나는 숫자 추가하고
            res.add(new ArrayList<>(temp)); // 결과에 추가
            temp.clear(); // 초기화

            if(i != arr.size()-1){ // 마지막 인덱스가 아니라면
                temp.add(arr.get(i+1)); // 그 다음 숫자 temp에 추가
                before = arr.get(i+1);
            }
        }    
    }

    temp.add(before);
    res.add(new ArrayList<>(temp));


    result = new int[res.size()][2];

    for(int i=0; i<res.size(); i++){
        result[i][0] = res.get(i).get(0);
        result[i][1] = res.get(i).get(1);
    }
    return result;

}

 

arr 리스트가 비어있지 않으면 시작한다.

첫 숫자와 이전 숫자를 지정해준다.

temp 리스트에 첫 숫자를 넣어준다. -> temp = [첫 숫자]

 

반복문

만약 다음에 나올 숫자가 이전 숫자와 이어지는 숫자이면 Inteval이 이어지므로 before ++

아니라면 새로운 Inteval이 나왔다는 의미이다.

따라서 temp에 before을 추가하고 추가하던 List를 마무리 짓는다.

그리고 결과에 추가한 후 temp 초기화.

또, 마지막 인덱스가 아니라면 새로운 Interval의 시작이므로 다시 temp에 추가를 시작한다.

 

위 과정을 arr 배열 끝까지 반복한 후 

마지막엔 temp가 마무리 지어지지 않은 채로 남아있게 된다. 

따라서 temp에 before을 저장해주고 결과 배열을 마무리 지어준다.

 

그리고 나서 결과 List를 2차원 배열로 바꾸어 준 후 반환해준다. 

---

결   과  :

class SummaryRanges {
    private List<Integer> arr;

    public SummaryRanges() {
        arr = new ArrayList<>();
    }
    
    public void addNum(int value) {
        if(!arr.contains(value)) arr.add(value);
    }
    
    public int[][] getIntervals() {
        ArrayList<List<Integer>> res = new ArrayList<>();
        int[][] result;
        List<Integer> temp = new ArrayList<>();
        int before;
        
        Collections.sort(arr);


        if(arr == null) return null;

        // 첫 초기화
        before = arr.get(0);
        temp.add(arr.get(0));

        for(int i=0; i<arr.size()-1; i++){
            if(arr.get(i+1) == before+1){ // 다음 숫자가 연결된 숫자라면
                before++;
            }
            else if(arr.get(i+1) != before+1){ // 다음 숫자가 연결된 숫자가 아니라면
                temp.add(before); // 끝나는 숫자 추가하고
                res.add(new ArrayList<>(temp)); // 결과에 추가
                temp.clear(); // 초기화

                if(i != arr.size()-1){ // 마지막 인덱스가 아니라면
                    temp.add(arr.get(i+1)); // 그 다음 숫자 temp에 추가
                    before = arr.get(i+1);
                }
            }    
        }

        temp.add(before);
        res.add(new ArrayList<>(temp));


        result = new int[res.size()][2];

        for(int i=0; i<res.size(); i++){
            result[i][0] = res.get(i).get(0);
            result[i][1] = res.get(i).get(1);
        }
        return result;

    }
}

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