BOJ 19623 회의실배정4

안예진·2021년 4월 12일

BOJ

목록 보기

1/8

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	// 클래스 생성
	static class lecture implements Comparable<lecture>{
		int start; //시작시간
		int end; //종료시간
		int person; //인원수
		
		public lecture(int start, int end, int person) {
			super();
			this.start = start;
			this.end = end;
			this.person = person;
		}

		@Override
		public int compareTo(lecture o) {
			return this.end - o.end;
					
		}
		
		
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		lecture[] lectureList = new lecture[N]; //회의 객체 리스트
		int[] startEnd = new int[2*N]; // 시작,종료시간 리스트 (2*N 개)
		HashMap<Integer,Integer> simplify = new HashMap<>(); //key:시간, val:순서
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine()," ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			lectureList[i] = new lecture(start,end, Integer.parseInt(st.nextToken()));
			startEnd[2*i] = start;
			startEnd[2*i+1] = end;
		}
		//좌표 압축 : 사용하는 숫자만 idx를 매겨서 숫자범위를 줄인다
		Arrays.sort(startEnd); // 오름차순정렬
		int idx = 0; // 사용하는 숫자의 개수
		for (int i : startEnd) {
			if(!simplify.containsKey(i)) { // 해당숫자가 처음 들어온다면
				simplify.put(i, idx++); //simplify에 넣어주기
			}
		}

		//EX 좌표 압축 예시
		// startEnd = [10, 50, 20, 60, 20, 110, 80, 100, 110, 140]
		// Arrays.sort(startEnd) = [10,20,20,50,60,80,100,110,110,140];
		// simplify = {10:0, 20:1, 50:2, 60:3, 80:4, 100:5, 110:6, 140:7};	

		int[] dp = new int[idx]; //dp도 idx만큼만 만들기
		int lectureIdx = 0;
		Arrays.sort(lectureList); // 종료시간 오름차순
		
		for (int i = 1; i < idx; i++) {
			int end = lectureList[lectureIdx].end; // 종료시간
			if(i== simplify.get(end)) { //확인한 회의가 현재시점에서 끝난다면...
				// 시작시간전에 값과 현재회의 인원을 합친 값을 가지고 업데이트!
				int current = dp[simplify.get(lectureList[lectureIdx].start)] + lectureList[lectureIdx].person;
				if(dp[i-1]<current)
					dp[i] = current;
				else // 안된다면 바로 이전값을 그대로 세팅
					dp[i] = dp[i-1];
				lectureIdx++; // 다음 회의로 넘어가기
			}else { //현재 시점에서 끝나는 회의가 없다면 이전값 그대로 세팅
				dp[i] = dp[i-1];
			}
			
		}
		
		System.out.println(dp[idx-1]);
	}

}