[문제풀이] 09-03. 결혼식

인프런, 자바(Java) 알고리즘 문제풀이

Greedy Alogorithm - 0903. 결혼식

---

🗒️ 문제

---

🎈 나의 풀이

	private static int solution(int[] start, int[] end) {
        int[] arr = new int[72];

        for(int i=0; i<start.length; i++) {
            for(int j=start[i]; j<end[i]; j++) {
                arr[j]++;
            }
        }

        return Arrays.stream(arr).max().getAsInt();
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] start = new int[n];
        int[] end = new int[n];

        for(int i=0; i<n; i++) {
            start[i] = sc.nextInt();
            end[i] = sc.nextInt();
        }

        System.out.println(solution(start, end));
    }

---

🖍️ 강의 풀이

  class Time implements Comparable<Time>{
      public int time;
      public char state;
      Time(int time, char state) {
          this.time = time;
          this.state = state;
      }
      @Override
      public int compareTo(Time ob){
          if(this.time==ob.time) return this.state-ob.state;
          else return this.time-ob.time;
      }
  }

  class Main {
      public int solution(ArrayList<Time> arr){
          int answer=Integer.MIN_VALUE;
          Collections.sort(arr);
          int cnt=0;
          for(Time ob : arr){
              if(ob.state=='s') cnt++;
              else cnt--;
              answer=Math.max(answer, cnt);
          }
          return answer;
      }

      public static void main(String[] args){
          Main T = new Main();
          Scanner kb = new Scanner(System.in);
          int n=kb.nextInt();
          ArrayList<Time> arr = new ArrayList<>();
          for(int i=0; i<n; i++){
              int sT=kb.nextInt();
              int eT=kb.nextInt();
              arr.add(new Time(sT, 's'));
              arr.add(new Time(eT, 'e'));
          }
          System.out.println(T.solution(arr));
      }
  }

---

💬 짚어가기

해당 문제는 Greedy Algorithm를 이용하여 푸는 문제다. 그러나 나의 풀이에서는 약간의
편법(?)으로 문제를 해결해보았다. 정석적인 접근법은 강의 코드를 참고바란다.

문제에서 주어진 최대 크기는 10만 건이고, 제한 시간은 1.5s이였다. 시간 복잡도가 $n^2$인
알고리즘을 사용하면 제한 시간을 넘길 것이다.

하지만 결혼식의 피로연 일정이 72시간으로 고정인 것을 확인하고 단순 반복문으로 구현하여
테스트 케이스를 통과했다. (10만 건 테스트에서는 1162ms의 실행 시간이 나왔다.)

구현으로 크기가 72인 배열을 하나 생성하고, 주어지는 입장 시간부터 퇴장 시간 사이의 인덱스
요소 값을 증가시킨 뒤, 배열에서 가장 큰 값을 갖는 인덱스(시간)를 반환하여 문제를 해결했다.

Greedy Alogorithm으로 풀기
강의에서는 입장과 퇴장을 시간으로 표현하 하나로 묶고, 이를 구분할 수 있는 state를 두었다.

모든 사건을 시간순으로 정렬한 뒤 스택과 유사한 방식으로 해당 시간에 들어오고 나가는 인원
수를 카운트하여 문제를 해결하였다.

이 때 시간이 같은 경우 퇴장을 앞에 오도록 정렬하는 것이 포인트다.