백준 1931 회의실 배정
백준 1931 회의실 배정
간단한 그리디 알고리즘 문제다.
그러나 한번에 정답을 맞추진 못했다ㅜㅜ 한번에 맞출 수 있도록 기록하고 다음에는 이런 실수 없도록 하자
문제를 읽어보면 어떤 식으로 풀어야 할지 바로 느낌이 오는 문제다.
하나의 회의실에서 여러개의 회의를 진행하는데, 하나의 회의가 진행되는 동안 다른 회의는 진행이 불가능하다.
단, 끝나는 시간과 동일하게 시작하는 회의는 진행이 가능하다.
이 점을 유의하면서 최대한 많이 회의를 할 수 있도록 하여 진행되는 회의의 최대 개수를 구하면 되는 코드다.
가장 먼저 제출했던 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
/**
* BOJ 1931 회의실 배정
* @author JOMINJU
*
* 각 회의에 대해 시작시간과 끝이 정해져 있고, 하나의 회의실에서 할 수 있는 회의의 최대 개수를 구해라
*
* 이차원 배열의 두번째 인덱스를 중심으로 배열 정렬
* 이후 끝나는 시간이 가장 이른 회의부터 진행
* 진행할 수 있는 회의 중 끝나는 시간이 가장 이른 회의부터 진행을 반복하여 회의 개수 구함
*/
public class Main {
public static BufferedReader br;
public static StringBuilder sb;
public static StringTokenizer st;
public static int meetingCount;
public static int[][] meetingTimes;
public static boolean[] check;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
meetingCount = Integer.parseInt(br.readLine().trim());
meetingTimes = new int[meetingCount][2];
check = new boolean[meetingCount];
for(int idx = 0; idx < meetingCount; idx++){
st = new StringTokenizer(br.readLine().trim());
meetingTimes[idx][0] = Integer.parseInt(st.nextToken());
meetingTimes[idx][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(meetingTimes, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2){
return o1[1]-o2[1];
}
});
int startTime = meetingTimes[0][1];
int result = 1;
check[0] = true;
for(int cnt = 1; cnt < meetingCount; cnt++){
if(meetingTimes[cnt][0] >= startTime && !check[cnt]){
check[cnt] = true;
startTime = meetingTimes[cnt][1];
result++;
cnt = 0;
}
}
sb.append(result);
System.out.println(sb);
}
}
여기서 내 바보같은 점이 보이는가? ㅜㅜ
바로 1. cnt = 0; , 2. 내 Comparator 코드다.
1번 코드는.. 생각없이 그냥 '처음으로 돌리면 되겠지 어차피 그리디 알고리즘이니까 헤헿ㅎ' 하며 집어넣었던 코드다.
반성합니다...ㅜㅜ 그냥 아무 생각 없이 처음으로 돌린다는 생각은 제발 이걸 본보기 삼아 앞으로 하지 않도록 하자...
그리고 2번의 내가 정렬한 Comparator 코드를 보면, 이차원 배열의 두번째 인덱스를 오름차순으로 정렬한 걸 볼 수 있다.
이때는 아무 생각 없이 이차원 배열에서 두번째 인덱스를 기준으로 정렬하면 일차원은 알아서 오름차순으로 정렬되겠지 하면서 하나의 코드만 집어넣었었다.
정말 최악의 사고방식이다.
당연히 첫번째 인덱스에 대해서도 오름차순으로 정렬해주어야 한다.
내가 뒷 부분의 for문에서 그냥 차례대로 한바퀴 쭉 돌면서 체크를 하도록 설정을 해놨기 때문에 처음부터 정렬이 깔끔하게 되어 있어야 저 부분에서 문제없이 코드가 돌아갈 수 있다.
이런 부분을 수정해서 최종적으로 제출한 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
/**
* BOJ 1931 회의실 배정
* @author JOMINJU
*
* 각 회의에 대해 시작시간과 끝이 정해져 있고, 하나의 회의실에서 할 수 있는 회의의 최대 개수를 구해라
*
* 이차원 배열의 두번째 인덱스를 중심으로 배열 정렬
* 이후 끝나는 시간이 가장 이른 회의부터 진행
* 진행할 수 있는 회의 중 끝나는 시간이 가장 이른 회의부터 진행을 반복하여 회의 개수 구함
*/
public class Main {
public static BufferedReader br;
public static StringBuilder sb;
public static StringTokenizer st;
public static int meetingCount;
public static int[][] meetingTimes;
public static boolean[] check;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
meetingCount = Integer.parseInt(br.readLine().trim());
meetingTimes = new int[meetingCount][2];
check = new boolean[meetingCount];
for(int idx = 0; idx < meetingCount; idx++){
st = new StringTokenizer(br.readLine().trim());
meetingTimes[idx][0] = Integer.parseInt(st.nextToken());
meetingTimes[idx][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(meetingTimes, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2){
return o1[1] != o2[1] ? o1[1] - o2[1] : o1[0] - o2[0];
}
});
int startTime = meetingTimes[0][1];
int result = 1;
check[0] = true;
for(int cnt = 1; cnt < meetingCount; cnt++){
if(meetingTimes[cnt][0] >= startTime && !check[cnt]){
check[cnt] = true;
startTime = meetingTimes[cnt][1];
result++;
}
}
sb.append(result);
System.out.println(sb);
}
}
앞으로는 절대 안일한 생각 금지, 알아서 되겠지라는 마인드 금지를 가지고 열심히 문제를 더 풀어야겠다ㅜㅜ 노력하자