[백준] 문제 11000번 그리디_강의실 배정

[백준] 문제 11000번 그리디_강의실 배정

정답률 29.158%의 문제이다.

그렇게까지 어려운 문제는 아닌데 내가 풀은 방법보다 시간이 더 적게 걸리는 방법이

존재할 것 같은 문제이다.

내가 짠 코드의 시간 효율성은

O(2n * log n) + O(n * log n) = O(n * log n)이다.

시간 효율성은 이것보다 크게 개선시키는 방법은 없을터이다.

room에 넣기전에 s,t를 일단 배열로 정렬해야하므로..

정렬에서만 O(n * log n)을 사용한다.

아래의 코드는 파이썬이다.

from heapq import heappush, heappop import sys input = sys.stdin.readline n = int(input()) time = [] for i in range(n): s, t = map(int, input().split()) time.append((s, t)) time.sort(key=lambda x: (x[0], x[1])) room = [] heappush(room, time[0][1]) for i in range(1, n): s, t = time[i] if s >= room[0]: heappop(room) heappush(room, t) print(len(room))

파이썬은 역시 데이터 다룰때 너무 편하다.. 여기서는 편하게 sort key 조건을 정해서 정렬하면 되지만..

아래 자바 코드를 보자

import java.util.*; import java.io.*; class Time { int start; int end; public Time(int start, int end) { this.start = start; this.end = end; } } class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; int n = Integer.parseInt(br.readLine()); Time[] time = new Time[n]; for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); time[i] = new Time(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); } Arrays.sort(time, (Time t1, Time t2) -> t1.start == t2.start ? t1.end - t2.end : t1.start - t2.start); PriorityQueue room = new PriorityQueue<>(); room.offer(time[0].end); for (int i = 1; i < n; i++) { if (time[i].start >= room.peek()) room.poll(); room.offer(time[i].end); } System.out.println(room.size()); } }

이게 자바코드다.

파이썬과 대충 비교만 해도 귀찮은 코드들이 증가한다.

일단 그래도 Sort, PriorityQueue를 연습할 수 있었던 좋은 문제였다.

from http://yuni0822.tistory.com/95 by ccl(A) rewrite - 2021-10-13 16:27:37