[자바] 백준 4055 - 파티가 좋아 파티가 좋아 (java)

 문제 : boj4055

---

 

필요 알고리즘 개념

• 정렬, 그리디
  
  • 더 범위가 좁은 것 부터 차례차례 골라나가면 풀 수 있다. 

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 문제에서 좀 애매한 부분부터 짚고 넘어가보자.

 

- "시작시간과 끝시간이 같은 파티가 주어질 수도 있다."

-> 최소 30분간은 참여해야하므로, 참여할 수 없는 파티이다. 버려도 되는 입력값이다.

 

- "아무리 늦게 끝나도 24시에는 끝나게 된다."

-> 따라서 24시대에는 파티 참여가 불가하다.

 

---

 

  9시 파티에 참여한다고 한다면, 9시00분과 9시30분 두 개에 참여할 수 있다. 즉, 이하에서 'N시 파티에 참여'했다면 'N시의 파티 또는 N시30분에 참여'한 것이다.

 

  끝나는 시간에는 파티에 참여가 불가하다. 만약 s가 9, e가 10이었다면 9시 파티에만 참여 가능하고 10시 파티엔 참여 불가하다. -> 그러니 코드에서는 s, e를 입력받을 때 s, e-1로 입력받았다.

 

  파티와 시간대를 이분 그래프로 나타낼 수 있으므로 이분매칭으로도 풀 수 있을 것 같다. 어쨌든 지금은 그리디로 풀꺼다. 각 시간대별로 2개씩 파티를 고른다고 생각해보자. 8시 파티부터 23시 파티까지 고르면 된다. 그렇다면 8 -> 23까지 증가하는 순서대로 파티를 찾는다면 어떻게 고르는게 가장 많이 고를 수 있을까?

 

  일단 파티가 끝나는 시간이 지난다면 해당 파티는 절대 못간다. (예를들어 어떤 파티의 e가 9인데 현재 10시 파티를 고르고 있다면 절대 고를 수 없다.) 그러니 e가 증가하는 순서대로 정렬한다. 그리고 e가 동일할 때 s의 정렬순서는 어떻게하면 좋을까? 고를 수 있는 가능성이 더 적은 것 부터 고르는게 더 좋을 것이다. 따라서 e가 증가하는 순서, e가 같다면 s가 감소하는 순서로 정렬한다. 이후 8~23까지 보면서 해당 시간에 가능한 파티를 정렬한 순서순으로 2개씩 골라주면 된다. 물론 어떤 시간엔 1개만 고를수도 있고, 아예 못고를수도 있다.

 

  예를들어 예제 입력 1의 첫 번째 케이스를 살펴보자.

8
12 13
13 14
12 13
9 10
9 10
12 13
12 14
9 11
0

  위에서 말한대로 e ASC, s DESC로 정렬하면 아래와 같다.

[9, 9]
[9, 9]
[9, 10]
[12, 12]
[12, 12]
[12, 12]
[13, 13]
[12, 13]

 

 

8시

X

 

9시

[9, 9]
[9, 9]
[9, 10]
[12, 12]
[12, 12]
[12, 12]
[13, 13]
[12, 13]

 

10시

[9, 9]
[9, 9]
[9, 10]
[12, 12]
[12, 12]
[12, 12]
[13, 13]
[12, 13]

 

11시

X

 

12시

[9, 9]
[9, 9]
[9, 10]
[12, 12]
[12, 12]
[12, 12]
[13, 13]
[12, 13]

 

13시

[9, 9]
[9, 9]
[9, 10]
[12, 12]
[12, 12]
[12, 12]
[13, 13]
[12, 13]

 

14시~23시

X

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    class Party implements Comparable<Party> {
        int s, e;
        public Party(int s, int e) {
            this.s = s;
            this.e = e;
        }

        @Override
        public int compareTo(Party o) {
            if (this.e == o.e)
                return o.s - this.s;
            return this.e - o.e;
        }
    }
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int tc = 1;
        while (true) {
            int p = Integer.parseInt(br.readLine());
            if (p == 0) break;
            new Main().solution(tc++, p);
        }
        System.out.print(sb);
    }

    public void solution(int tc, int p) throws Exception {
        List<Party> arr = new ArrayList<>();
        for (int i = 0; i < p; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken()) - 1;
            if (s > e) continue;
            arr.add(new Party(s, e));
        }
        Collections.sort(arr);

        int cnt = 0;
        for (int t = 8; t <= 23; t++) {
            for (int d = 0; d < 2; d++) {
                for (int i = 0; i < arr.size(); i++) {
                    Party cur = arr.get(i);
                    if (cur.s <= t && cur.e >= t) {
                        cnt++;
                        arr.remove(i);
                        break;
                    }
                }
            }
        }

        sb.append(String.format("On day %d Emma can attend as many as %d parties.\n", tc, cnt));
    }
}