[백준/JAVA] 1931번: 회의실 배정

🔺 문제

1931번: 회의실 배정

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        int[][] A = new int[N][2];
 
        for(int i = 0 ; i < N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            A[i][0] = Integer.parseInt(st.nextToken());
            A[i][1] = Integer.parseInt(st.nextToken());
        }
 
        // 종료 시간 기준 정렬
        Arrays.sort(A, new Comparator<int[]>() {
            @Override
            public int compare(int[] S, int[] E) {
                if(S[1] == E[1]) {    // 🔔 종료 시간이 같으면, 시작 시간 빠른 순 정렬 
                    return S[0] - E[0];
                }
                return S[1] - E[1];
            }
        });
 
        int cnt = 0;
        int end = -1; 
        for(int i = 0 ; i < N ; i++) {
            // 겹치지 않는 경우. 종료 시간 업데이트
            if(A[i][0] >= end) {    
                end = A[i][1];
                cnt++;
            }
        }
 
        System.out.println(cnt);
    }
}

✅ 해결 아이디어
✔ 그리디
1) 종료 시간 순 정렬
→ 종료 시간이 같을 때는, 시작 시간 기준으로 정렬
2) 시간이 겹치지 않는 회의가 나오는 경우 선택

 

💥 유의사항

⇨ 종료 시간이 같을 경우, 시작 시간이 빠른 순서로 정렬하는 로직 추가해야

⇨ 함수 재정의 / 사용자 정의 정렬 방법

 

 

---

🔺 다른 풀이들

- 설명 복습용..

[백준] 1931번 : 회의실배정 - JAVA [자바]

 

 

- 사용자 정의 정렬 (람다식 ver.)

[Algorithm] 백준 1931번_회의실 배정(Java)

Arrays.sort(A, (o1, o2) -> {
    if(o1[1] == o2[1])
    	return o1[0] - o2[0];
    return o1[1] - o2[1];
});

---

💬 느낀 점

사용자 정의 정렬이 들어간 문제를 여러 개 풀어보자

 

 

1회독	2회독	3회독	4회독	5회독
V	6.19	12.1	12.23	240222

 

(+ 6.19 2회독)

우선순위 큐를 이용해봤다. (참고)

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        
        PriorityQueue<Meeting> pq = new PriorityQueue<>();
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            
            pq.add(new Meeting(s, e));
        }
        
        
        int prev = 0;   // 📍 이전 회의 end 시간
        int cnt = 0;
        
        for(int i = 0 ; i < N ; i++) {
            Meeting tmp = pq.poll();
            
            if(prev <= tmp.start) {
                cnt++;
                prev = tmp.end;
            }
        }
 
        System.out.println(cnt);
        
    }
}
 
class Meeting implements Comparable<Meeting> {
    int start;
    int end;
    
    Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }
    
    @Override
    public int compareTo(Meeting m) {
        if(this.end == m.end)   return this.start - m.start;    // 🚨 끝나는 시간이 같다면 시작 시간이 빠른 회의부터
        else                    return this.end - m.end;        // 끝나는 시간이 빠른 회의부터
    }
}

start와 end 시간 변수를 갖는 Meeting 클래스를 만들고,

우선순위 큐를 이용해서 end 시간 기준 오름차순으로 정렬하게 했다.

 

근데 여기서 유의사항! 

🚨  종료 시간이 같다면, 시작 시간이 빠른 순으로 정렬하게 하고,

종료 시간이 다르다면, 종료 시간이 빠른 순으로 정렬하게 해야 한다.

 

 

 

 

(+ 12.1 3회독)

정렬 기준 찾다가 시간 많이 흘려보냄ㅠ

풀고 보니 종료 시간만 기록해두면 돼서 시작 시간 기록하는 변수는 필요가 없다네요

코드 확인하기

import java.util.*;
import java.io.*;
 
class Meeting implements Comparable<Meeting> {
    int s, e;
    
    public Meeting(int s, int e) {
        this.s = s;
        this.e = e;
    }
 
    @Override
    public int compareTo(Meeting mm) {
        if(this.e != mm.e)    // 종료 시간이 다르다면, 종료 시간 순 정렬
            return this.e - mm.e;
        return this.s - mm.s;    // 종료 시간이 같다면, 시작 시간 순 정렬
    }
}
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        Meeting[] m = new Meeting[N];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            
            m[i] = new Meeting(s, e);
        }
        Arrays.sort(m);    // 사용자 정의 정렬
        
        int tmpS = m[0].s;
        int tmpE = m[0].e;
        int cnt = 0;
        
        for(int i = 1 ; i < m.length ; i++) {
            if(tmpE <= m[i].s) {
                tmpS = m[i].s;
                tmpE = m[i].e;
                cnt++;
            }
        }
        
        System.out.println(cnt + 1);
    }
}
 

 

 

(+12.23 4회독)

정렬하는 부분에서 띠용하고 85%에서 정체되어서 반례 찾아보고 그랬다,,ㅠ

코드 확인하기

import java.util.*;
import java.io.*;
 
class Node implements Comparable<Node> {
    int s, e;
    
    public Node(int s, int e) {
        this.s = s;
        this.e = e;
    }
    
    // 회의 종료 시간 기준 오름차순 정렬. 🔔 종료 시간이 같다면, 시작 시간 순 오름차순 정렬
    @Override
    public int compareTo(Node n) {
        if(this.e != n.e) {
            return this.e - n.e;
        }
        return this.s - n.s;
    }
}
 
public class Main {
    static int N;
    static Node[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        arr = new Node[N];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            
            arr[i] = new Node(s, e);
        }
        Arrays.sort(arr);   // 종료 시간 순 정렬
        
        int cnt = 0;
        int end = -1;
        
        for(int i = 0 ; i < N ; i++) {
            if(arr[i].s >= end) {
                end = arr[i].e;
                cnt++;
            }
        }
        
        System.out.println(cnt);
    }
}