[백준] 회의실 배정 / 1031번 / 파이썬 / Python / 정렬 / 그리디

 

 

탐욕법 욕심쟁이

 

그리디 알고리즘(Greedy Algorithms)이란? 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 것을 결정하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다.

 

💡solutions )

💬 sorted() 정렬 메소드를 사용했다-> 정렬기준은 종료시간, 시작시간 순으로 정렬

💬 이전 회의의(before) 종료시간을 rooms[0][1]로 잡고, 반복문을 통해 그 다음 회의의 시작시간과 비교하여 시작시간이 이전 회의의 종료시간보다 늦거나 같으면 가능회의 수를 (cnt)+=1 하고 before 값을 갱신해준다.

💬 처음 구현한 코드에서는 정렬 기준을 시작 시간으로, 또 이중 포문으로 모든 회의의 가능 여부를 모두 확인했기 때문에 시간 초과가 났다. (시간 초과가 나시는 분들은 이 두 가지를 확인하시면 좋을 것 같습니다.)

 

 

🎫code )

import sys

input = sys.stdin.readline

rooms = []
for i in range(int(input())):
    a, b = map(int, input().split(' '))
    rooms.append([a, b])

rooms = sorted(rooms, key=lambda x: (x[1], x[0]))
before = rooms[0][1]
cnt = 1
for room in rooms[1:]:
    s, e = room[0], room[1]
    if s >= before:
        cnt += 1
        before = e
print(cnt)

 

📌 description )

문제출처 : www.acmicpc.net/problem/1931

1931번: 회의실배정

 

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.