MeetingRoom

-개발환경-

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

-문제-

 [[s1,e1],[s2,e2],...] (si < ei) 와 같이 , 시작과 끝의 시간으로 구성된 회의시간 배열이 주어졌을때 ,
한 사람이 모든 회의에 참여할 수 있는지 여부를 bool 로 리턴하시오.

 

ex)

Input: [[0,30],[5,10],[15,20]]
Output: false
Input: [[7,10],[2,4]]
Output: true

 

-접근법-

주어진 [startTime,endTime] 모음 배열들이 서로 겹치는지 확인하여야 한다.

1. brute force 방식으로

n-1 + n-2 n-3 ... +n-(n-1) =n*(n-1)+ ((n-1)(n-2)) /2  = (n-1)(n+(n-2)/2)  =

거의 n**2 형태만큼의 반복횟수로 확인하여도 되고,

 

2. startTime 을 기준으로 배열을  오름정렬한다.

정렬되었다면 나름 시작 시간 기준으로 오름정렬이 된 것이고,

뒤.startTime > 앞.endTime 이 만족된다면 정상적인것 ,  불만족시 false 리턴.

시간복잡도는 O(정렬+N-1)

 

-MeetingRooms.java-

package codingTest;
 
import java.util.Arrays;
import java.util.Comparator;
 
 
class Interval{
    int start;
    int end;
    Interval(){
        this.start = 0;
        this.end =0;
    }
    Interval(int s, int e){
        this.start = s;
        this.end = e;
    }
}
public class MeetingRooms {
    public static void main(String[] args) {
        MeetingRooms a = new MeetingRooms();
        
        //Testcase 1 
        Interval in1=new Interval(15,20);
        Interval in2=new Interval(0,30);
        Interval in3=new Interval(5,10);
        Interval in4=new Interval(10,20);
        Interval in5=new Interval(2,24);
        Interval[] intervals = {in1,in2,in3,in4,in5};
        System.out.println(a.solve(intervals));//false
    
        //Testcase 2
        Interval in2_1=new Interval(7,10);
        Interval in2_2=new Interval(2,6);
        Interval[] intervals2 = {in2_1,in2_2};
        System.out.println(a.solve(intervals2));//true
        
    }
    
    public boolean solve(Interval[] intervals) {
        //오름차순정렬
        if(intervals==null) return false;
        Arrays.sort(intervals,Comp);
        
        //진위검사
        for(int i=1; i<intervals.length; i++) {
            if(intervals[i-1].end > intervals[i].start)
                return false;
        }
        return true;
    }
    
      Comparator<Interval> Comp = new Comparator<Interval>() { //Comparator을 구현하는익명객체 생성 
          public int compare(Interval o1, Interval o2) { 
              return o1.start-o2.start;  // 0 or 양수 리턴시 객체자리변경  ,    음수리턴시 자리변경x 
          };
      };
    
    
    public void print(Interval[] intervals) {
        for (int i =0; i<intervals.length; i++) {
            Interval in= intervals[i];
            System.out.println(in.start+" "+in.end);
        }
    }
}

-Description

43 : Comp방식으로 정렬 , Arrays는 배열관련 유용한 클래스
46~50 : 접근법 2번 방식의  '뒤.startTime > 앞.endTime ' 적용
53~57: Interface Comparator을 구현하는 익명객체를 생성하여 compare메소드를 오버라이딩(오름차순적용)
60~65: 배열을 단순출력해주는 메소드

-추가개념-

객체의 정렬 기준을 명시하는데는 두가지 방법이 존재.
1. Interface Comparable을 구현 하는 방법
기본 정렬로 문제를 해결할 경우 이용
2. Interface Comparator을 구현 하는 방법(글에서 사용한 방법)
기본 정렬 기준과 다르게 구현하고 싶을때 이용

Compareator를 implements후 compare메소드를 오버라이딩 할시 유의사항.
public int compare(Interval o1, Interval o2) 에서 
- 기존에 o1 , o2(오름차순) 순서로 정렬할 것이라고 생각. 
- 만약 , compare 의 반환 값이 양수or 0이면 , 인자의 순서변경발생
- compare 의 반환 값이 음수이면 , 인자 순서 유지
- 위 3가지 개념을 이용해 사용자정의 정렬이 가능.

- ex) start를 기준으로 , 내림차순정렬을 만들어보자
 public int compare(Interval o1, Interval o2){
     if( o1.start < o2.start )
          return 0;
     else
          return -1;
}
같은 표현으로
 public int compare(Interval o1, Interval o2){
     if( o1.start > o2.start )
          return -1;
     else
          return 0;
}
-출력결과-
start 의 기존순서 : 15, 0, 5, 10, 2 
변경된 순서 : 15 , 10 , 5 ,2, 0 으로

 

-마침글-

인용