문제 유형
회의는 시작 시간과 종료 시간이 주어진다.
가장 많이 회의를 배정받게 되는 수를 구하라.
조건(시작 시간 <= 종료 시간)
//예시 입력
5
1 4
2 3
3 5
4 6
5 7
// 출력
3
(2,3), (3,5), (5,7) 세개의 회의를 배정받는 것이 가장 많은 회의를 배정받게 되는 수이다.
greedy 알고리즘이란?
각 단계에서 최적의 선택을 하는 것으로,
지금 당장 최선의 선택을 계속해서 하며 전체적인 최적해를 찾는 알고리즘이다.
조금 풀어서 설명해보자면
현재 단계에서 다음 단계를 보고 최선인지 아닌지를 파악해서
최선이 아니라면 선택하지 않고, 최선이라면 선택하는 방식이다
예를 들어,
주식 투자를 한다고 가정해보자.
지금 최저 가격이라고 판단하고 매수를 했는데, 가격이 더 떨어진다면 그건 최선의 선택이 아니라고 볼 수 있다.
그런데 어찌 예측할 수 있겠는가?
그저 지금 선택할 수 있는 최선의 선택을 하는 수 밖에 없는 것이다.
그게 greedy 알고리즘이다.
필요 핵심 자료구조
int n // (자연수 갯수),
int arr[] // (n개 만큼 자연수 입력),
int L // (현재 레벨),
int sum // (현재 레벨의 sum 값),
int total // (arr 배열 값을 모두 더한 값),
boolean flag // (total - sum = sum일 때 true),
DFS() 메서드 // 핵심 로직,
answer // 출력,
문제 풀이 과정
처음에는 문제를 시작 시간을 기준으로 오름차순했다.
그래서인지 다양하게 나올 수 있는 경우마다 조건문을 남발하게 되었고
결과적으로 아래와 같은 코드가 탄생(?)하였다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Discuss implements Comparable<Discuss>{
public int s;
public int e;
public Discuss(int s, int e){
this.s = s;
this.e = e;
}
@Override
public int compareTo(Discuss o){
return this.s - o.s;
}
}
public class 회의실배정 {
public int solution(ArrayList<Discuss> arr, int n){
int cnt = 1;
Collections.sort(arr);
int temp = arr.get(0).e;
for(int i = 0; i < n; i++) {
if(i != 0 && arr.get(i).s == arr.get(i).e){
if(i == n-1){
cnt++;
}else{
temp = arr.get(i+1).s;
cnt++;
}
}else{
if(temp < arr.get(i).e){
if(temp == arr.get(i).s){
temp = arr.get(i).e;
cnt++;
}
}else if(temp > arr.get(i).e){
temp = arr.get(i).e;
}
}
}
return cnt;
}
public static void main(String[] args) {
회의실배정 T = new 회의실배정();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
ArrayList<Discuss> arr = new ArrayList<>();
for(int i = 0; i < n; i++){
int s = in.nextInt();
int e = in.nextInt();
arr.add(new Discuss(s, e));
}
System.out.print(T.solution(arr, n));
}
}딱봐도 if문이 남발되어 사용되고 있고,
코드를 구현한 나조차도 코드를 분석을 해야하는 지경이었다.
5개의 문제 case중 3개는 맞췄지만,
문제를 제출하기 전까지도 이 코드 방식이 옳지 않다는걸 느낄 수 있었다.
결국 강의를 봤다.
greedy에 대한 문제 풀이 경험이 적다는 것을 가장 큰 문제라고 판단했고
greedy의 알고리즘 패턴을 익히는 것에 집중해야하는 단계라고 느꼈기 때문이다.
즉, 학습의 단계라고 생각이들었다.
지금은 응용의 단계가 아니었다.
강의에서는 기본적으로 종료시간을 오름차순으로 두었다.
그래서 종료시간이 다음 회의의 시작 시간보다 같거나 크다면
배정받을 수 있는 회의로 판단한다는 것이었다.
그래서 종료시간을 기준으로 오름차순으로 두어서 조건문을 세워봤는데 문제가 원활하게 풀리지 않았다.
3
3 3
1 3
2 3
위와 같이 입력되었을 때 종료시간이 모두 같기 때문에 오름차순이 적용되지 않고,
회의실 배정은 단 한번으로 마무리된다.
하지만 실질적으로 회의실 배정은 두번이 가능하다.
그것은 현재 종료시간과 다음 종료시간이 같을 때 시작 시간을 오름차순으로 두면 가능해진다.
아래와 같이 말이다.
3
1 3
2 3
3 3
그렇게 하기 위해선 Comparable<> 인터페이스를 구현하는 compareTo() 메서드에 아래와 같이 선언해줘야 한다.
@Override
public int compareTo(Discuss o){
if(this.e == o.e) return this.s - o.s;
else return this.e - o.e;
}
핵심 코드
// Comparable<> 인터페이스를 구현하는 Discuss 클래스
class Discuss implements Comparable<Discuss>{
public int s;
public int e;
public Discuss(int s, int e){
this.s = s;
this.e = e;
}
@Override
public int compareTo(Discuss o){
if(this.e == o.e) return this.s - o.s;
else return this.e - o.e;
}
}
// greedy 알고리즘이 적용된 solution
public int solution(ArrayList<Discuss> arr){
int cnt = 1;
Collections.sort(arr);
int tempE = arr.get(0).e;
for(Discuss o : arr){
if(tempE <= o.s){
tempE = o.e;
cnt++;
}
}
return cnt;
}피드백, 개선할 점
첫째 greedy 문제를 접한 경험이 많이 없다는게 가장 큰 문제였다.
greedy 문제를 두번째 풀어보는 단계였고,
greedy 알고리즘의 패턴을 아직 명확하게 이해하지 못한 상태였다.
그래서 조건문을 남발하는 문제가 있었다.
느낀점
첫번째 greedy 알고리즘의 허점은 현재 단계에서 최적의 선택만을 선택한다는 것이다.
시간복잡도는 O(n)으로 효율적일지는 모른다.
하지만,
인생도 그렇듯이 현재 단계에서 최적의 선택을 반복한다고 해서
결과가 항상 좋을 수는 없듯이.
greedy 알고리즘 또한 마찬가지다.
내가 느끼기에 greedy 알고리즘은 허점이 아주 많은 알고리즘이다.
하지만, 시간 복잡도 차원에서 바라보자면 좋은 선택지가 될 수 있다.
