[백준/JAVA] 4055번: 파티가 좋아 파티가 좋아

문제 보러가기

4055번: 파티가 좋아 파티가 좋아

[문제 풀이]

파티는 8:00에 시작해서 24:00에 끝난다.

여기서 8시부터 30분간격으로 파티를 참석할 수 있고, 예외적으로 8:00에 시작해서 8:00에 끝나는 파티는 참석으로 친다.

그렇다면 8시부터 30분간격으로 파티를 참석한 것을 어떻게하면 저장할 수있는지 방법을 제시한다면 각 시간대를 배열로 만든다.

시간대

8:00~8:30

8:30~9:00

9:00~9:30

9:30~10:00

10:00~10:30

10:30~11:00

위와 같이 각 시간대에 해당하는 배열을 만들면 되는데, 파티는 오전 8시부터 오후 12시까지 이기때문에 모든 시간대를 합하면 32개의 시간대로 나눌 수 있다. 이제 시간대를 어떻게 저장할지 알기 때문에 저장을 하면 되는데, 이때 시작 시간과 끝나는 시간이 같은 파티는 참석할 수 있는 파티로서 받아들이면 된다. 그리고 저장을 하기전에 정렬을 해야한다. 정렬을 하는 이유가 있다.

시작 시간	종료 시간
12	14
12	13
12	13

위의 입력을 정렬을 하지 않는 예시로 든다.

만약 12~14시간대가 먼저 나온다면 12:00~12:30를 저장하게 되고 이렇게 되면 12~13은 12:30~13:00시간대 한개만을 가질 수 있기 때문에 참석할 수 있는 파티는 총 2개가 된다. 정답은 3개이다.

그렇기 때문에 정렬을 해야한다.

시작 시간	종료 시간
12	13
12	13
12	14

위는 정렬을 한 입력이다. 12:00~12:30, 12:30~13:00, 13:00~13:30을 참석할 수 있기때문에 정답은 3개이다.

또한 정렬을 할 때 시작시간과 종료시간의 차이가 작은 것부터 오름차순으로 정렬해야 한다.

시간의 차이가 작은 것부터 시간대를 저장해야 더 많은 파티를 참석할 수 있다.

 

[코드]

import java.io.*; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; 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));         StringTokenizer st;         StringBuilder sb = new StringBuilder();         int count = 1;         int p = Integer.parseInt(br.readLine());         while (p != 0) {             Party[] party = new Party[p];             int[] time = new int[32]; //시간대             int answer = 0;             for (int i = 0; i < p; i++) {                 st = new StringTokenizer(br.readLine());                 party[i] = new Party(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));             }             Arrays.sort(party, Comparator.comparingInt(o -> (o.end - o.start)));             for (int i = 0; i < p; i++) {                 int start = party[i].start;                 int end = party[i].end;                 if (start == end) answer++; //시작과 끝이 같다면 참석할 수있는 파티이다.                 for (int j = start; j < end; j++) {                     if (time[(j - 8) * 2] != 1) {                         time[(j - 8) * 2] = 1;                         break;                     }                     if (time[(j - 8) * 2 + 1] != 1) {                         time[(j - 8) * 2 + 1] = 1;                         break;                     }                 }             }             for (int i = 0; i < time.length; i++) {                 if (time[i] == 1) answer++;             }             sb.append("On day ").append(count++).append(" Emma can attend as many as ").append(answer).append(" parties.").append("\n");             p = Integer.parseInt(br.readLine());         }         bw.write(sb.toString());         bw.close();     } } class Party {     int start, end;     Party(int start, int end) {         this.start = start;         this.end = end;     } }