MergeInterval

-개발환경-

IDE : Eclipse IDE for Java Developers Version: 2020-03 (4.15.0) 공부 자료 :  www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94/lecture/22652

-문제-

인터벌들의 모음이 주어질때 , 인터벌의 오버래핑되는 모든 부분을 통합해라.
ex)
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

 

-접근법-

접근법 
1. 한 인터벌을 (start,end)로 명명할 때 , start를 기준으로 오름차순 정렬을 수행
2. before이라는 인터벌을 담을 객체를 생성후 정렬된 인터벌중 가장 앞 값을 집어 넣는다.
3. 정렬된 인터벌모임을 반복문으로 돌린다. 반복문 내용으로,
case1) before.end >= current.start 일시 ,
before의 start와 end를 갱신 .
 (이와같이 명료히 할 수 있는 이유는 초기에 정렬을 해주었기에)
case2) before.end < current.start 일시 ,
before을 result에 저장.
현재의 current를 before로 만듬
4. for문 종료 이후 , before를 result에 저장.

 

그림으로 나타낸 절차는 아래와 같다.

 

 

-MergeInterval.java-

package codingTest;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
 
class Interval_{
    int start;
    int end;
    Interval_(){start=0;end=0;}
    Interval_(int s,int e){start=s;end=e;}
    
}
 
public class MergeInterval {
 
    public static void main(String[] args) {
        //TestCase
        Interval_ in2=new Interval_(1,3);
        Interval_ in1= new Interval_(2,6);
        Interval_ in3= new Interval_(8,10);
        Interval_ in4= new Interval_(15,18);
        
        List<Interval_> intervals= new ArrayList<>();
        intervals.add(in1);
        intervals.add(in2);
        intervals.add(in3);
        intervals.add(in4);
 
        //Procedure
        MergeInterval a= new MergeInterval();
        List<Interval_> list= a.merge(intervals);  
        //OutPut
        System.out.println("==========================================");
        a.print(list);
    }
    public List<Interval_> merge(List<Interval_> intervals){
        if (intervals.isEmpty()) return intervals;
        //1.ds
        List<Interval_> result= new ArrayList<>();
        
        //sort
        print(intervals);//test
        Collections.sort(intervals, (a,b)->a.start-b.start);//람다표현식 오름차순
        //Collections.sort(intervals,comp ); //기존방식
        System.out.println("==========================================");
        print(intervals);//test
        
        //2
        Interval_ before = intervals.get(0);//[1,3]
        for(int i=1;i<intervals.size();i++) {
            Interval_ current= intervals.get(i);
            if(before.end >= current.start) {
                before.end=Math.max(before.end,current.end);
            }else {
                result.add(before);
                before=current;
            }
        }
        
        if(!result.contains(before)) { //해당 if 문은 없어도 무방해보임, 단 내부 명령어는 쓰여져야 함
            result.add(before);
        }
        
        return result;
    }
    
    void print(List<Interval_> list) {
        for(int i=0;i<list.size();i++) {
            Interval_ in =list.get(i);
            System.out.println(in.start +" "+in.end);
            
        }
    }
    Comparator comp = new Comparator<Interval_>() {
        public int compare(Interval_ a,Interval_ b) {
            return a.start-b.start;
        }
    };
}
 

-Description

 

25 : TestCase 객체들을 담을 ArrayList인 intervals을 생성한다.
33 : 구현한 merge함수를 이용하여 문제를 해결한후 결과값 반환
39 : input이 없을 경우 처리
41 : 결과를 담을 ArrayList 형 result 생성
45 : 람다표현식으로  intervals를 start을 기준으로 하여 오름차순으로 정렬
51~64 : 접근법에서 설명한 내용이다.
66 : 결과 result 반환
76 : 람다식을 이용한 정렬을 수행하였으므로 , 이 함수는 이용하지 않았다.

결과화면

-추가개념-

List , ArrayList , Collections , Lambda 표현식

 

List는 인터페이스 그리고,  ArrayList 및 ,LinkedList,Stack,Vector 는 클래스로 List를 구현.

//List 인터페이스
     //순서 o  , 중복 허용  ex)대기자 명단
     //ex)
          //ArrayList,LinkedList,Stack,Vector등
     //메소드 (자세 한건 JAVA8 API 문서볼것)
          //add -추가
          // get,set  - 얻어오기, 저장하기.
          //indexOf - 검색  (왼쪽부터 오른쪽으로)
          //lastIndexOf - 검색 (오른쪽부터 왼쪽으로)
          //sort  -정렬
          //subList - from부터 to 까지 뽑아옴

          //int size() - size반환

          //isEmpty - 비어있는지 확인

          //boolean contains(Object o) - 지정된 객체가 존재하는지 확인
     //ArrayList - 동기화 처리가 안되어 있다. -
          //vector는 동기화 처리가 되어있다.
          //데이터의 저장공간으로 배열을 사용한다. ( Object 배열 )
          //메소드
               //생성자
                    //ArrayList()
                    //ArrayList(Collection c)
                    //ArrayList(int initialCapacity) -배열의 길이 넣어줌-
               //boolean add(Object o)
               //void add(int index,Object element)
               //boolean addAll(Collection c)
               //boolean addAll(int index , Collection c)
               //boolean remove(Object o)
               //Object remove(int index)
               //boolean removeAll(Collection c)
               //void clear() - 모든객체삭제
               //int indexOf(Object o) - 찾으면 인덱스반환 , 못찾으면 -1 반환
               //int lastIndexOf(Object o) - 오른쪽부터 찾음
               //boolean contains(Object o) - 지정된 객체가 존재하는지 확인
               //Object get(int index) - 객체 읽기
               //Object set(int index, Object element) - 수정
               //List subList(int fromIndex,int toIndex) - from부터 to 전까지 객체들을 뽑아서 새로운 리스트를 반환
               //Object[] toArray()  - ArrayList가 가지고 있는 객체 배열을 반환
               //boolean isEmpty() - 비어있는지 확인
               //void trimToSize() - 빈공간 제거
               //int size()  -ArrayList에 저장된 객체의 갯수를 반환

 

Collections 는 정적메소드들의 집합으로 구성된 클래스이다.
//여기에는 컬렉션에서 작동하는 다형성 알고리즘이 포함되어 있다.
1. reverse() 메서드 - 뒤집기
2. sort() 메서드 - 정렬하기
3. copy() 메서드 - 복사본만들기
4. shuffle 메서드 - 무작위로 섞기

 

-람다(Lambda)표현식-
람다표현식은 함수형 인터페이스를 통해서 사용할수 있다.
함수형 인터페이스는 추상 메소드가 한개뿐인 메소드이다..
자바에서는 @FunctionalInterface 를 인터페이스구문위에 적어서 구분한다고 한다..
람다표현식은 , 파라미터,화살표, 바디(구현부분) 3가지로 나뉜다.
람다 표현식은
1. () -{}
2. () ->"history"
3. () -> {return "history";}
4. 파라미터->{return "history"+a;}
5. (파라미터,파라미터)->"history" 
바디(구현부분)에는 return문에 적힐 문장이 온다. return은 생략가능..
파라미터 타입도 생략이 가능..
 return 을 적어줄시 {} 을 써야하며 ; 도 붙여줘야한다..

 

 

-마침글-

 

 

인용