[Softeer/소프티어] 강의실 배정(그리디 : Greedy) - 자바[Java]

https://softeer.ai/practice/6291

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

풀이

기본적인 그리디 문제다.

• 강의가 끝나는 시간으로 정렬
• 빨리 끝나는 것부터 먼저 함(선택)
• 그 다음 강의 시작시간이, 그 전 강의 종료시간보다 크거나 같으면 선택
• 종료시간 오름차순으로 정렬한 다음, 시작시간 오름차순으로 정렬되도록 한다.

로직

1. 강의의 시작시간과 종료 시간을 저장하기 위한 클래스 Lecture를 만든다. Lecture는 종료시간 오름차순으로 정렬한 다음, 시작시간 오름차순으로 정렬되도록 한다.

2. 강의의 개수 n을 입력받는다.

3. 강의의 정보를 저장할 List<Lecture> lectures를 선언한다.

4. n개의 강의의 시작시간과 종료시간을 입력받는다.

5. lectures를 정렬한다.

6. 종료시간이 빠른 것부터 먼저 선택한 다음, 그 다음 강의 시작시간이 그 전 강의 종료시간보다 크거나 같으면 선택한다.

7. 선택한 강의 개수를 출력한다.

 

코드

import java.util.*;
import java.io.*;


public class Main
{
    static class Lecture implements Comparable<Lecture> {
        int s;
        int f;

        public Lecture(int s, int f) {
            this.s = s;
            this.f = f;
        }

        @Override
        public int compareTo(Lecture o) {
            if (this.f == o.f) return this.s - o.s;
            return this.f - o.f;
        }

    }

    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        List<Lecture> lectures = new ArrayList<>();

        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int f = Integer.parseInt(st.nextToken());

            lectures.add(new Lecture(s, f));
        }

        Collections.sort(lectures);

        int cnt = 0;
        int time = 0;
        for (Lecture lecture : lectures) {
            if (time <= lecture.s) {
                cnt++;
                time = lecture.f;
            }
        }

        System.out.println(cnt);
    }
}

 

Reference

알고리즘 - 그리디 알고리즘(Greedy Algorithm)

https://loosie.tistory.com/515

💡 현재 시점에서 최선으로 가장 좋은 것을 선택하는 것 → Greedy
이 순간 나의 최선의 선택
어떤 기준에 의해서 정렬하고, 앞에서부터 주욱 선택해나가는 것 ⇒ Greedy 기법