[Greedy] 문제 이름 : University Career Fair - 사용자 정의 클래스 객체 정렬

문제 설명

A team organizing a university career fair has a list of companies along with their respective arrival times and their duration of stay. Only one company can present at any time. Given each company's arrival time and the duration they will stay, determine the maximum number of presentations that can be hosted during the career fair.

 

사용 개념

그리디, 객체 정렬 

 

문제 해결 아이디어

주어진 시간동안 최대한 많은 발표를 해야하므로 그리디 알고리즘을 적용한다. 이를 위해 주어진 회사들을 오름차순 정렬해야 하는데, 이때 정렬 기준은 '발표가 끝나는 시간'을 기준으로 한다. 왜냐하면 문제에서 배열로 주어진 시작 시간과 진행 시간을 기준으로 오름차순 정렬 시에는 최대값이 반환되지 않기 때문이다. 

예시) arrival = [1, 2, 3] finish = [4, 3, 5] 일 때

         if 시작 시간 기준 정렬 시

            (1,4)만 가능, return 1 --> 최대값 X

         if 끝나는 시간 기준 정렬 시 

            (2,3) (3,5) 가능, return 2 --> 최대값 ! 

 

코드

import java.util.*;

class Result {
    /*
     * Complete the 'maxEvents' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER_ARRAY arrival
     *  2. INTEGER_ARRAY duration
     */
     public static int maxEvents(List<Integer> arrival, List<Integer>
duration) {
    // Write your code here
        List<Pair> companies = new LinkedList<>(); // ㄴ
        for(int i = 0; i < arrival.size(); i++){
            Pair p = new Pair(arrival.get(i), arrival.get(i) +
duration.get(i));
            companies.add(p);
        }
        Collections.sort(companies); // ㄷ 

        int count = 1;
        int endTime = companies.get(0).endTime;
        for(int i = 1; i < companies.size(); i++){ // ㄹ 
            if(companies.get(i).startTime < endTime) continue;
            else{
                count++;
                endTime = companies.get(i).endTime;
            }
        }   
        return count;
    }
}
class Pair implements Comparable<Pair>{ // ㄱ 
    int startTime;
    int endTime;

    public Pair(int startTime, int endTime){
        this.startTime = startTime;
        this.endTime = endTime;
    }
    
    @Override
    public int compareTo(Pair p){
        if((this.endTime - p.endTime) == 0) //끝나는 시간이 동일할 때 
            return this.startTime - p.startTime; //시작 시간이 빠른 것 기준 
        else
            return this.endTime - p.endTime;
    }
}

ㄱ. 시작 시간과 종료 시간을 멤버변수로 갖는 Pair 클래스 

→ 객체 정렬을 위한 Comparable<T> 인터페이스를 구현함 

     compareTo(T o) 메소드 오버라이딩  

ㄴ. Pair 클래스 타입의 연결리스트 생성 

ㄷ. 정렬을 위한 java.util.Collections의 sort() 메소드 사용

ㄹ. ㄷ에 의해 오름차순 정렬된 리스트에서 하나씩 객체를 꺼내 계산하기 

 

추가 개념 정리

* 사용자 정의 클래스 객체 정렬 

자바에서 리스트 정렬 시 java.util.Collections 클래스의 static 메소드 sort()를 사용함

위의 2가지 메서드를 사용하기 위한 2가지 방법이 존재함

1. sort(List<T> list) : Comparable 인터페이스 구현 후  compareTo(T o) 메소드 오버라이딩 

2. sort(List<T> list, Comparator<? super T> c) : Comparator 인터페이스 구현 후 compare(T o1, T o2) 메소드 오버라이딩 

→ 메소드 오버라이딩을 통해 객체 정렬 기준을 정의함 

→ 내림차순 정렬 시 or 주어진 클래스의 정렬 기준을 변경할 수 없을 때 주로 2를 사용함

 

객체 정렬 기준의 필요성)

숫자나 문자와 같은 기본형(primitive) 데이터는 Natural Order에 따라 자바가 자동으로 정렬해줌

하지만 특정 타입의 객체는 기본형 데이터와 달리 정렬 기준이 없으면 정렬을 할 수가 없으므로, 정렬 기준을 정의하여 알려줘야 함

 

[예시를 통한 구현]

public class Pair {
    private int startTime;
    private int endTime;

    public Pair(int startTime, int endTime){
        this.startTime = startTime;
        this.endTime = endTime;
    }
    
    public int getStartTime() {
    	return startTime;
    }
    
    public void setStartTime(int startTime) {
    	this.startTime = startTime;
    }
    
    public int getEndTime() {
    	return endTime;
    }
    
    public void setEndTime(int endTime) {
    	this.endTime = endTime;
    }
}

→ 새롭게 정의한 클래스 

→ 해당 클래스 타입의 객체 정렬 기준 : endTime 기준 오름차순 (endTime이 동일하다면, startTime 기준 오름차순) 

 

구현1) Comparable 인터페이스 구현 & compareTo() 메서드 오버라이딩 

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

class PairComparable implements Comparable<PairComparable>{

    private int startTime;
    private int endTime;

    public PairComparable(int startTime, int endTime){
        this.startTime = startTime;
        this.endTime = endTime;
    }
    
    public int getStartTime() {
    	return startTime;
    }
    
    public void setStartTime(int startTime) {
    	this.startTime = startTime;
    }
    
    public int getEndTime() {
    	return endTime;
    }
    
    public void setEndTime(int endTime) {
    	this.endTime = endTime;
    }

    @Override
    public int compareTo(PairComparable o) {
        if(this.endTime - o.endTime == 0)
            return this.startTime - o.startTime;
        else 
            return this.endTime - o.endTime;
    }
}

public class ComparableEx{
	public static void main(String[] args) {
		List<PairComparable> list = new LinkedList<PairComparable>();
		
		PairComparable p1 = new PairComparable(1,4);
		PairComparable p2 = new PairComparable(2,3);
		PairComparable p3 = new PairComparable(3,5);
		
		list.add(p1);
		list.add(p2);
		list.add(p3);
		
		Collections.sort(list);
		
		for(PairComparable p : list) {
			System.out.println(p.getStartTime() + " " + p.getEndTime());
		}
	}
}

정렬 결과

* compareTo() 메서드의 반환값 의미

현재 객체의 값 < 인자로 전달된 객체의 값 : return 음수

현재 객체의 값 == 인자로 전달된 객체의 값 : return 0

현재 객체의 값 > 인자로 전달된 객체의 값 : return 양수

→ 기본이 오름차순 정렬이므로, 반환값이 음수이거나 0이면 순서 변화가 없고, 양수인 경우에만 두 객체의 순서가 바뀜 

 

구현2) Comparator 인터페이스 구현 & compare() 메서드 오버라이딩 

→ public void sort(List<T> list, Comparator<? super T> c)를 사용하면 주어진 Comparator 인터페이스를 구현한 클래스에서 정의한 정렬 기준으로 전달된 리스트를 정렬함  

 

구현2-1) 새로운 클래스로 생성

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

class PairComparator{
    private int startTime;
    private int endTime;

    public PairComparator(int startTime, int endTime){
        this.startTime = startTime;
        this.endTime = endTime;
    }
    
    public int getStartTime() {
    	return startTime;
    }
    
    public void setStartTime(int startTime) {
    	this.startTime = startTime;
    }
    
    public int getEndTime() {
    	return endTime;
    }
    
    public void setEndTime(int endTime) {
    	this.endTime = endTime;
    }
}

//구현2-1) 새로운 클래스로 생성 
class MyComparator implements Comparator<PairComparator>{
	@Override
	public int compare(PairComparator o1, PairComparator o2) {
		if(o1.getEndTime() - o2.getEndTime() == 0)
			return o1.getStartTime() - o2.getStartTime();
		else
			return o1.getEndTime() - o2.getEndTime();
	}
	
}

public class ComparatorEx {
	public static void main(String[] args) {
		List<PairComparator> list = new LinkedList<PairComparator>();
		
		PairComparator p1 = new PairComparator(1,4);
		PairComparator p2 = new PairComparator(2,3);
		PairComparator p3 = new PairComparator(3,5);
		
		list.add(p1);
		list.add(p2);
		list.add(p3);
		
		Collections.sort(list, new MyComparator());
		
		for(PairComparator p : list) {
			System.out.println(p.getStartTime() + " " + p.getEndTime());
		}
	}		
}

→ Comparator를 구현한 MyComparator 클래스를 새로 생성함 

 

구현2-2) 익명 클래스 사용

//구현2-2) 익명 클래스 사용 
public class ComparatorEx2 {
	public static void main(String[] args) {
			List<PairComparator> list = new LinkedList<PairComparator>();
			
			PairComparator p1 = new PairComparator(1,4);
			PairComparator p2 = new PairComparator(2,3);
			PairComparator p3 = new PairComparator(3,5);
			
			list.add(p1);
			list.add(p2);
			list.add(p3);
			
            //익명 클래스 
			Comparator<PairComparator> myComparator = new Comparator<PairComparator>() {
				@Override
				public int compare(PairComparator o1, PairComparator o2) {
					if(o1.getEndTime() - o2.getEndTime() == 0)
						return o1.getStartTime() - o2.getStartTime();
					else
						return o1.getEndTime() - o2.getEndTime();
				}	
			};
			
			Collections.sort(list, myComparator);
			
			for(PairComparator p : list) {
				System.out.println(p.getStartTime() + " " + p.getEndTime());
			}
	}
}

→ Comparator를 구현한 클래스를 새로 생성하지 않고 main 메서드 내에서 익명 클래스를 사용함 

실행 결과

 

* 익명 클래스 

사용 이유 : 일회성의 클래스를 따로 생성할 필요없이 바로 사용할 수 있음

사용 방법 : 메서드 내에 선언

부모클래스/인터페이스 인스턴스 = new 부모클래스/인터페이스(){};

→ 부모클래스 or 인터페이스의 인스턴스를 생성하면서 {}안에 처리 구문을 넣어줌. 이때 필요하다면 메소드 오버라이딩함.

→ 생성된 인스턴스는 익명클래스의 인스턴스가 되어 오버라이딩된 메소드를 실행함(새로운 클래스 생성한 거랑 동일한 역할 수행)

주의 사항 : 익명클래스에서 생성된 메서드나 필드는 익명클래스 밖에서는 접근 불가! 

 

참고)

https://www.daleseo.com/java-comparable-comparator/

http://www.tcpschool.com/java/java_collectionFramework_comparable

https://wjheo.tistory.com/entry/Java-정렬방법-Collectionssort

https://beginnersbook.com/2017/08/comparable-interface-in-java-with-example/

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Comparator.html