728x90
반응형
[백준 1931] 회의실 배정
문제 출처 : 링크
그리디 알고리즘에 해당하는 문제다.
즉, 최적의 해를 찾기 위한 알고리즘을 짜야하는데, 반례를 잘 찾아가면서 풀어야 한다.
작년에 풀었던 문제였지만, 다시 풀어봐도 반례를 다 생각하지 못해서 상당히 고생했다ㅠ
가장 많은 회의를 진행할 수 있도록 하려면, 가장 빨리 끝나는 회의를 찾아야 한다는 걸 알아내야 한다. 이런 문제는 그냥 많이 풀어보면서 어느정도 감을 익히는게 제일 좋지 않은가 싶다...
나는 우선 class를 하나 만들어 회의에 대한 시작 시간과 종료 시간을 저장했다.
그리고 각 회의 정보를 하나의 리스트에 저장했고, 회의 종료 시간이 빠른 순으로 보기 위해서 Comparator를 활용해 종료시간 오름차순으로 정렬했다.
(이때 int값을 활용해서 오름차순 하기 위해서는 변수를 Integer로 선언해야했음)
여기서 끝인 줄 알았으나, 아래와 같은 반례를 찾지못해 시간이 좀 걸렸다.
회의가 3번일 때
3 3
2 3
3 3
회의의 시작 시간과 종료 시간이 같을 수도 있기 때문에 3 3이 두번 있으면 둘다 모두 동시에 회의가 가능하다. 따라서 답은 3이 출력돼야 한다.
하지만 그냥 이걸 종료 시간으로 sorting 해버리면, 동시에 진행되는 회의 중 하나가 오름차순으로 제대로 정렬되지 못한 채 짤려버리고 2번만 가능하다고 나왔다. 하나의 조건문이 더 필요했다.
1 2 3 4 5 6 7 | public int compare(Seminar s1, Seminar s2) { if(s1.getEnd() != s2.getEnd()){ return s1.getEnd().compareTo(s2.getEnd()); } else return s1.getStart().compareTo(s2.getStart()); } | cs |
만약 종료 시간이 같은 회의가 존재한다면, 시작 시간으로 한번더 정렬을 해주면서 해결이 가능했다.
전체 소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.StringTokenizer; class Seminar { // 회의 시작, 끝 저장할 클래스 Integer start; Integer end; Seminar(Integer start, Integer end) { this.start = start; this.end = end; } public Integer getStart(){ return start; } public Integer getEnd(){ return end; } /* @Override public String toString() { return "(" + start + ", " + end + ")"; } */ } class ArrSort implements Comparator<Seminar>{ // comparator로 끝나는 시간 정렬 @Override public int compare(Seminar s1, Seminar s2) { if(s1.getEnd() != s2.getEnd()){ return s1.getEnd().compareTo(s2.getEnd()); } else return s1.getStart().compareTo(s2.getStart()); } } public class Problem1931 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ArrayList<Seminar> arr = new ArrayList<Seminar>(); int num = Integer.parseInt(br.readLine()); for (int i = 0; i < num; i++) { StringTokenizer st = new StringTokenizer(br.readLine(), " "); int start = Integer.parseInt(st.nextToken()); int end = Integer.parseInt(st.nextToken()); Seminar s = new Seminar(start, end); arr.add(s); } ArrSort arrSort = new ArrSort(); Collections.sort(arr, arrSort); // 정렬 int chkEnd = arr.get(0).end; int count = 1; // 회의 수 저장 변수(처음 값 저장하고 시작해서 1로 선언) for (int i = 1; i < arr.size(); i++) { int e = arr.get(i).end; int s = arr.get(i).start; if(chkEnd <= s){ chkEnd = e; count++; } } System.out.println(count); } } | cs |
728x90
반응형
'Algorithm > 백준(BOJ)' 카테고리의 다른 글
[백준 1261] 알고스팟 (Java, 다익스트라) (0) | 2019.02.23 |
---|---|
[백준 9663] N-Queen (Backtracking) (0) | 2019.02.17 |
[백준 1012] 유기농 배추 (DFS, BFS) (0) | 2019.02.17 |
[백준 6588] 골드바흐의 추측 (2) | 2019.02.06 |
[백준 10798] 세로 읽기 (2) | 2019.02.04 |