[소프티어] 강의실 배정 자바 풀이 레벨3 그리디알고리즘

 

백준 11000번 문제와는 다른문제입니다. 맨 아래 내용 참고해주세요~

 

 

 

 

 

 

 

 

 

처음에 뭘 하려했으나,

역시나 간단하게 생각하자 간단하게!!!!!

 

 

https://softeer.ai/practice/6291

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

 

 

 

 

 

 

 

문제스펙

 

 

 

 

핵심설명

- 첫번째 강의부터 dfs 돌려야되나 싶었다..10^6이라 시간초과....

5
1 9999999
2 3
3 4
4 5
5 6

 

- 정렬하고 그리디 알고리즘 적용해야함

5
2 3
3 4
4 5
5 6
1 9999999

 

- end 값으로 오름차순 후, start값으로 오름차순

- 직전강의end <= 현재강의start 이면, ++

- 중간에 겹친 놈이라면 continue;

 

현준이형 조언 감사합니다

 

 

 

 

 

 

 

정답코드

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

public class Main {

    public static int dap = 0;
    public static int n;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        int[][] cl = new int[n][2];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            cl[i][0] = a;
            cl[i][1] = b;
        }
        Arrays.sort(cl, (a,b) -> a[1]==b[1] ? a[0]-b[0] : a[1]-b[1]);
        

        // for(int i=0; i<n; i++){
        //     for(int j=0; j<2; j++){
        //         System.out.print(cl[i][j] + ",");
        //     }
        //     System.out.println();
        // }

        int beforeB = -1;
        for(int i=0; i<n; i++){

            int a = cl[i][0];
            int b = cl[i][1];
            if(a >= beforeB){
                dap++;
                beforeB = b;
            }else{
                continue;
            }
        }
        
        bw.write(String.valueOf(dap));
        bw.close();
    }

    // public static void sol(int[][] g, int index, int cnt){
    //     int a = g[index][0];
    //     int b = g[index][1];
    //     // 내 현재 위치는 index이고, a~b강의를 배정한 상황인데

    // }
}

 

 

 

 

 

 

참고로,

백준 문제 11000 와 문제 내용이 다릅니다. (백준은 강의실이 n개만큼 존재함)

아래 링크 참고.

https://sookr5416.tistory.com/276

[자바로 푸는 백준] 11000번 강의실 배정