[java] 문제 035 (백준 1931)

문제

회의실 배정

 

교재 풀이

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class P1931_회의실배정 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[][] A = new int[N][2];
    for (int i = 0; i < N; i++) {
      A[i][0] = sc.nextInt();
      A[i][1] = sc.nextInt();
    }
    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 count = 0;
    int end = -1;
    for (int i = 0; i < N; i++) {
      if (A[i][0] >= end) { // 겹치지 않는 다음 회의가 나온경우
        end = A[i][1]; // 종료시간 업데이트
        count++;
      }
    }

    System.out.println(count);
  }
}

 

내 풀이) 24.6.19에 풀고 시간 오버로 미완성

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());
		
		ArrayList<int[]> a=new ArrayList<>();
		for(int i=0;i<n;i++){
		    StringTokenizer st=new StringTokenizer(br.readLine());
		    int s=Integer.parseInt(br.readLine());
		    int e=Integer.parseInt(br.readLine());
		    
		    a.add(new int[2] {s, e});
		}
		
		Collections.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 now=a.remove(0)[1];
		int cnt=1;
		for(int i=1;i<n;i++){
		    now=a.remove(0);
		    if()
		}

	
}

구현하던 부분
    
    정렬 완료 후 최대 회의 개수를 구하는데 
        어떻게? 회의 개수는 십만 번이야. 그럼 10만번 반복문 돌려서 해야 할까? 
        최악의 케이스? n의 제곱은 아닐 수 있는게 n행의 각 열은 크기가 2뿐이라서
        그럼 for n번 반복하면서 
            현재 진행 중인 회의 담는 변수 now 
                즉 일단 제일 앞에 있는 회의 하나 꺼내서 담기 
                자료구조는 글쎄. 시작시간과 종료 시간을 둘 다 담아야 하나? 
                그냥 종료시간만 담으면 되지 않을까? 
            그리고 계속 a 원소를 꺼내면서 
                꺼낸 회의가 now와 안 겹치면 
                즉 now의 종료시간보다 꺼낸 회의의 시작 시간을 비교해서 
                꺼낸 회의 시작 시간이 now보다 크거나 같으면 
                이 꺼낸 회의를 now로 업데이트해주기 
                만약 겹칠 땐 계속 continue로 구현하기 
            그럼 회의가 now에 담길 때마다, cnt도 ++해주는 걸 추가해주면 되네 
    
    그 후 cnt를 출력해주면 정답이 나옴 







 N개의 회의
    각 회의 I에 대해 시작시간과 끝나는 시간
    각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수
예외 처리
    한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 
     회의의 시작시간과 끝나는 시간이 같을 수도 있다.
     =>이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
 
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)
둘째 줄부터 N+1 줄까지 각 회의의 정보
    회의의 시작시간과 끝나는 시간
    int 범위, 0 이상인 수 
최대 사용할 수 있는 회의의 최대 개수를 출력

접근법
    티스토리 메모 보고 와서 그걸 이용하면 
        종료 시간이 빠른 걸 먼저 하는 게 회의를 가장 많이 할 수 있음 
        그래서 종료 시간 오름차순으로 정렬하고 
        만약 종료 시간 같은 경우 시작 시간이 큰 거, 즉 회의 길이가 짧은 거 우선 
        이걸  Arrays.sort(a, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b)
        })
    그럼 종료 시간 빠른 걸 기준으로 오름차순으로 정렬했으면  그 다음으로 
        뭐 하지? 최대 개수를 출력해야 하는 거잖아 
        계속 계속 하면서, n이 10의 5제곱이니까 n 제곱 시간 복잡도는 10의 10제곱이라 아웃 
        그럼 조건에 안 맞으면 continue하는 부분이 필요하네
        조건은 뭐지? 어떤 조건? 그러니까 
            제일 앞의 회의가 방을 사용한다면 -> 기 기간까진 다른 회의 못하니까 
            그 시간 가운데 겹치는 회의는 다 contiunue를 해야 겠고 
            겹치지 않으면서 제일 먼저 있는 걸 또 사용해주고 
            이를 반복하면 되지 않을까 
    자료구조는?
        그러니까 a를 이차원 배열로 사용해야 하나 .
        그리고 각 행은 하나의 회의 시작과 종료 시간을 나타내고 
        예로 1 4인 건 어떻게 저장하고 표현하지?
            그냥 이차원 배열엔 {1 4} 형식의 배열이 쭉 있는 거지 
            그럼 a의 크기는 대략 a[n][2]겠네 
슈도코드 
    n을 입력받음 
    for n번 반복해서 
        회의 시간을 저장함 
            그러려면 a란 arrayList를 만듦, int[]자료구조에 대해서 
            또 a.add 함수 이용해서 {1 4} 형식의 int[] 생성해서 넣어주기 
            이런 식으로 저장해주고 
    
    그 다음 이 a 배열을 comparator를 이용해서 정렬해야 함 
        어떻게?
        그러니까 a 배열을 다시 정렬한다고 ? 
            일단 Collections.sort()를 이용해주고 
            두 번째 이수에 new comparator 생성해줘서 사용자 지정 기준을 만들고 
        정렬 기준은 어떻게 할 건데?
            일단 원리는 종료 시간이 빠른 게 먼저 오도록 오름차순 정렬을 하려고 하고 있고 
            종료 시간이 같은 예외적인 경운, 시작 시간이 종료 시간과 가까운 것,
            즉 시작과 종료 사이 길이 짧은 거가 먼저 오도록 해주기 
            => 이를 코드로 표현하면 
            compare를 오버라이드해줘서 public int compare(int[] a, int[] b)라 치면 
            if 종료시간이 같으면 
                return a[0]-b[0]
                    // 0번은 시작 시간이라 치면, 시작시간이 a가 5, b가 3이면 
                    // a가 5 5고 b가 3 5라면, 3 5 회의가 먼저 와야지 
                    // 그 다음 5 5도 올 수 있음 
            아니면 return a[1]-b[1]
                // 예로 5-3은 2고, 그럼 오름차순 정렬해란 소리. 왜? 
                // 1번은 종료 시간을 뜻하고, 종료 시간이 5인 것보단 3인 게 그리디에 맞으니 
    
    정렬 완료 후 최대 회의 개수를 구하는데 
        어떻게? 회의 개수는 십만 번이야. 그럼 10만번 반복문 돌려서 해야 할까? 
        최악의 케이스? n의 제곱은 아닐 수 있는게 n행의 각 열은 크기가 2뿐이라서
        그럼 for n번 반복하면서 
            현재 진행 중인 회의 담는 변수 now 
                즉 일단 제일 앞에 있는 회의 하나 꺼내서 담기 
                자료구조는 글쎄. 시작시간과 종료 시간을 둘 다 담아야 하나? 
                그냥 종료시간만 담으면 되지 않을까? 
            그리고 계속 a 원소를 꺼내면서 
                꺼낸 회의가 now와 안 겹치면 
                즉 now의 종료시간보다 꺼낸 회의의 시작 시간을 비교해서 
                꺼낸 회의 시작 시간이 now보다 크거나 같으면 
                이 꺼낸 회의를 now로 업데이트해주기 
                만약 겹칠 땐 계속 continue로 구현하기 
            그럼 회의가 now에 담길 때마다, cnt도 ++해주는 걸 추가해주면 되네 
    
    그 후 cnt를 출력해주면 정답이 나옴

 

설명

이해하는 데 어려움 없음