[JAVA] 1931번 - 회의실배정

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

앞 회의의 종료 시간과 뒤 회의의 시작 시간이 겹치지 않으면 된다!

그리고 활동을 많이 하려면 -> 종료시간이 빨라야 한다 

 

이 문제는 이 두가지만 주의하면된다! 

1. 시작 시간을 기준으로 오름차순 정렬을 하면 안된다

빨간색이 시작 시간이 빠르지만 종료 시간이 노란색 보다 늦게 끝나는데 그럼 3개를 고를 수 있는데 빨간색을 골라버리면 1개밖에 못 고른다. 그래서 시작시간 기준 정렬은 안됨

2. 회의시간을 기준으로 정렬하면 안된다

노란색이 회의시간이 더 긴데 시작 시간이 더 빠르면 2개를 고를 수 있는데 회의시간이 짧은 순서대로 정렬하면 빨간색 하나밖에 못고른다

 

그래서 종료 시간 기준으로 정렬을 해야한다. 

서로 겹치지 않는 활동에 대해 종료 시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다

 

 

 

시간복잡도

N번만큼 반복문을 돌려야하니까 O(N)이다. 시간내에 가능하다. 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1) 배열 정렬하기

이차원 배열로 시작시간, 종료시간을 받고 종료시간을 기준으로 오름차순 정렬하되, 종료 시간이 같으면 시작시간이 빠른 순으로 오름차순 정렬하면 된다.

Arrays.sort(time, new Comparator<int[]>() {
				
				@Override
				public int compare(int[] o1, int[] o2) {
					
					// 종료시간이 같을 경우 시작시간이 빠른순으로 정렬해야한다.  
					if(o1[1] == o2[1]) {
						return o1[0] - o2[0];
					}
					
					return o1[1] - o2[1];
				}
	 
			});

 

2) 최대 횟수 계산

직전 종료시간이 다음 회의 시작 시간보다 작거가 같다면 갱신하면 된다 

for(int i = 0; i < n; i++) {
				
				// 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신 
				if(prev_end_time <= time[i][0]) {
					prev_end_time = time[i][1];
					cnt++;
				}
			}

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

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 [][]time = new int[n][2];
	        
	        for(int i=0; i<n; i++) {
	        	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	        	time[i][0] = Integer.parseInt(st.nextToken());
	        	time[i][1] = Integer.parseInt(st.nextToken());
	        }
	        
	        Arrays.sort(time, new Comparator<int[]>() {
				
				@Override
				public int compare(int[] o1, int[] o2) {
					
					// 종료시간이 같을 경우 시작시간이 빠른순으로 정렬해야한다.  
					if(o1[1] == o2[1]) {
						return o1[0] - o2[0];
					}
					
					return o1[1] - o2[1];
				}
	 
			});
	        
	        int cnt = 0;
	        int prev_end_time = 0;
	        
	        for(int i = 0; i < n; i++) {
				
				// 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신 
				if(prev_end_time <= time[i][0]) {
					prev_end_time = time[i][1];
					cnt++;
				}
			}
			
			System.out.println(cnt);
	       
	        
	   }
}