BOJ - 시간 관리 1263번 (JAVA)

❓ 문제 - 백준 시간 관리 1263번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/1263)

1263번: 시간 관리

 

 

📝 문제해결법

1. 이 문제는 Greedy(탐욕법) + 정렬으로 알고리즘을 풀었다.

• 일을 끝내야 할 시간이 가장 큰 일에서 일을 끝내야 할 시간이 가장 작은 시간대로 차례대로 일을 끝마치면서 가장 늦게 일을 시작할 수 있는 시간을 구한다.
• work라는 2차원배열에서 (일을 끝내야할 시간)을 내림차순으로 정렬한다.
• answer = (일을 끝내야 할 시간 - 일이 걸리는 시간)에 시작하면 가장 늦게 일을 시작할 수 있으므로 정렬된 배열을 하나씩 돌면서 모든 일에서 가장 늦게 일을 시작할 수 있는 시간을 구하면 된다.
• 모든 일을 다 처리 했는데 가장 늦게 일을 시작할 수 있는 시간이 0보다 작은 마이너스이면 하루 안에 일을 처리 못 하므로 -1을 출력한다.

2. 자바의 문법적 사용

• BufferedReader, BufferedWriter을 통해 입출력의 시간단축을 한다.
• 자바의 배열의 정렬은 Arrays.sort()을 활용
• 다차원 배열의 경우, 인덱스 기준으로 정렬 할 때  "Arrays.sort(work, (o1, o2) -> o2[1] - o1[1]); 
  "으로 사용하면 해당 인덱스를 기준으로 내림차순 정렬의 사용법이다.

 

3. 문제를 풀면서 느낀점

• 처음엔, 일을 끝내야할 시간이 가장 작은 시간부터 차례대로 일을 처리해나갔는데, 그러면 그 시간에 일을 처리해야 하루 일을 모두 마칠 수 있는 경우를 고려 못 한 것이라는 걸 몰랐다.
• 탐욕법이므로, "주어진 문제의 조건인 가장 늦게 일을 시작할 수 있는"에 초점을 맞춰서 문제를 풀어야겠다고 다짐..
• 파이썬으로 알고리즘 풀다가 자바로 넘어갔는데 문법적으로 차이가 좀 있어서 해당 부분을 빠르게 익숙할 수 있게 노력해야겠다..(노력 = 많은 알고리즘 문제풀기..)

💻 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

	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());
		
		int[][] work = new int[n][n];
		
		for(int i=0;i<n;i++) 
		{
			String[] ts = br.readLine().split(" ");
			work[i][0] = Integer.parseInt(ts[0]);
			work[i][1] = Integer.parseInt(ts[1]);
		}
		
		Arrays.sort(work, (o1, o2) -> o2[1] - o1[1]);
		
		int answer = work[0][1] - work[0][0];
		
		for(int i=1;i<n;i++) 
		{
			if(work[i][1] < answer) 
			{
				answer = work[i][1];
			}
			answer -= work[i][0];
		}
		
		if(answer > 0) 
		{
			bw.write(String.valueOf(answer));
		} else 
		{
			bw.write(String.valueOf(-1));
		}
		
		bw.flush();
		bw.close();
		
	}

}