백준 1931 회의실

아래는 문제 링크입니다.

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

이 문제를 풀게 된 계기가 있다.

오늘 필자는  프로그래머스 스킬 체크를 하고 있었다. 빠르게 level 1을 통과하고 level 2에 돌입했다.

첫 번째 문제는 테스트 케이스가 한 3개? 정도 통과 안되었는데, 빠르게 예외 케이스를 찾아서 이를 수정했다.

그런데 이게 무슨일인지 모르겠는데, 두 번째 문제가 회의실과 비슷한 문제였다.

회의실이 특별히 기억에 남는 이유는 풀다가 포기하고 넘어가서다 ㅎㅎ.. 모든 경우의 수를 구하다가 포기한 걸로 기억한다.

그래서 역시나 프로그래머스 leve 2는 50점을 맞고 합격하지 못했다. 그래서 오늘 회의실을 학습하고 정리하기로 했다.

솔직히 자력으로 풀지 못했다. 구글에서 여러 자료들을 참고했다.

문제는 다음과 같다.

문제

입출력 예시

이런 문제를 그리디 알고리즘 문제이면서, 활동 선택 문제라고 한다.

'활동 선택 문제는 각각 시작 시간(si)과 종료 시간(fi)으로 표시된 활동 세트가 주어졌을 때 주어진 시간 범위 내에서 수행할 충돌하지 않는 활동 선택에 관한 조합 최적화 문제이다. 문제는 한 사람이 한 번에 한 가지 활동만 할 수 있다고 가정할 때 한 사람 또는 기계가 수행할 수 있는 최대 활동 수를 선택하는 것이다.'  라고 위키피디아에 나와있다.

해결책

• 서로 겹치지 활동이 겹치지 않으면서 종료 시간이 빠르면 더 많은 활동을 할 수 있는 시간이 많아진다.
• 많은 블로그 글과 활동 선택 문제 글을 보았는데, 이번 문제는 종료 시간을 기준으로 정렬을 해야 한다.
• 처음에는 잘 이해가 가지 않았는데, 종료 시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이  많아진다는 것을 보고 
  이번 그리디 알고리즘 문제에서 포인트는 종료시간이 빠른 것이라고 깨달았다.

아래는 풀이 코드다.

import java.io.*;
import java.util.*;

public class Main{
    public class Meeting implements Comparable<Meeting>{
        int start;
        int end;

        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Meeting o) {
            if(this.end == o.end) return this.start - o.start; //종료 시점이 같으면 시작 시간으로 정렬
            return this.end - o.end;
        }
    }

    public int solution()throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Meeting> list = new ArrayList<>();
        int num = Integer.parseInt(br.readLine());
        int answer = 0;

        for(int i = 0; i < num; i++){
            String[] s = br.readLine().split(" ");
            list.add(new Meeting(Integer.parseInt(s[0]),Integer.parseInt(s[1])));
        }
        Collections.sort(list);

        int previousEndTime = 0;

        for(int i = 0; i < num; i++){
            // 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신한다
            if(previousEndTime <= list.get(i).start){
                previousEndTime = list.get(i).end;
                answer++;
            }
        }

        return answer;

    }
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        System.out.println(main.solution());
    }
}

 

역시 다양한 문제를 접하는 것이 코딩 테스트 때 당황을 줄여주는 것 같다.

더 많은 문제를 풀어보자..!!

 

 

풀이를 참고한 자료

https://st-lab.tistory.com/145

https://velog.io/@akwnsldj1/%EB%B0%B1%EC%A4%801931%EB%B2%88-%ED%9A%8C%EC%9D%98%EC%8B%A4-%EB%B0%B0%EC%A0%95-JAVA%EC%9E%90%EB%B0%94

https://en.wikipedia.org/wiki/Activity_selection_problem