[BAEKJOON/Python] no.1931 회의실 배정 | Greedy

문제

---

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

1차 풀이

---

conference_count = int(input())
schedule = []
for conference in range(conference_count):
    schedule.append(tuple(map(int, input().split())))
schedule.sort(key=lambda tup: tup[0])

result = [[schedule[0]]]
for schedule_time in schedule[1:]:
    put = 0
    for idx, result_time in enumerate(result[:]):
        if result_time[-1][1] <= schedule_time[0]: #맨 마지막 회의 끝나는 시간 > 예정회의 시작시간
            result_time.append(schedule_time)
            put += 1
        elif idx == len(result) - 1 and put == 0:
            result.append([schedule_time])
answer = max(result, key=lambda time: len(time))
print(len(answer))

👉🏻일단 이중 for문을 돌리면서 각 회의 예정 시간에 맞춰 모든 스케쥴을 짜보았다.

conference_count = int(input())
schedule = []
for conference in range(conference_count):
    schedule.append(tuple(map(int, input().split())))
schedule.sort(key=lambda tup: tup[0])

print(schedule)
#[(0, 6), (1, 4), (2, 13), (3, 5), (3, 8), (5, 7), (5, 9), (6, 10), (8, 11), (8, 12), (12, 14)]

• schedule이라는 리스트에 각 회의 예정 시간들을 튜플로 담고 시작시간을 기준으로 정렬한다.

result = [[schedule[0]]]
for schedule_time in schedule[1:]:
    put = 0
    for idx, result_time in enumerate(result[:]):
        if result_time[-1][1] <= schedule_time[0]: #맨 마지막 회의 끝나는 시간 > 예정회의 시작시간
            result_time.append(schedule_time)
            put += 1
        elif idx == len(result) - 1 and put == 0:
            result.append([schedule_time])

• result 리스트에 schedule의 첫 번째 요소를 먼저 넣어준다.
• for 문을 통해 schedule 두 번째 요소(schedule_time)부터 확인을 한다. 
• result를 또 for문 돌리면서 schedule_time과 함께 비교한다.
  • result_time의 끝나는 시간보다 schedule_time의 시작 시간이 작거나 같으면 result_time에 schedule_time을 추가해준다. 그리고 put 변수에 1을 더해준다.
  • 그렇지 않고 put이 0이면 result에 schedule_time을 담은 리스트를 새로 넣어준다.

# [
#     [(0, 6), (6, 10), (12, 14)], 
#     [(1, 4), (5, 7), (8, 11), (12, 14)], 
#     [(2, 13)], 
#     [(3, 5), (5, 7), (8, 11), (12, 14)], 
#     [(3, 8), (8, 11), (12, 14)], 
#     [(5, 9), (12, 14)], 
#     [(8, 12), (12, 14)]
# ]

👉🏻그러면 result에 다음과 같이 가능한 스케줄이 모두 모인다.

answer = max(result, key=lambda time: len(time))
print(len(answer))

👉🏻그리고 result에 담긴 리스트들 중 길이가 가장 긴 요소를 answer에 담아 출력한다.

🐰일단 for문 떄문인지 시간 초과가 떴다ㅋㅋ

👉🏻문제점은 아래와 같다. 

1. 일단누가 봐도 그리디가 아니다!
   • 정답이 아닌 다른 스케쥴까지 고려하느라 시간이 많이 들어간다. 

 

2차 풀이 : Greedy 활용

---

conference_count = int(input())
schedule = []
for conference in range(conference_count):
    schedule.append(tuple(map(int, input().split())))
schedule.sort(key=lambda tup: (tup[1], tup[0]))

count = 1
end = schedule[0][1]
for schedule_time in schedule[1:]:
    if schedule_time[0] >= end:
        end = schedule_time[1]
        count += 1

print(count)

👉🏻코드는 다음과 같이 변경되었다.

schedule.sort(key=lambda tup: (tup[1], tup[0]))
print(schedule)
#[(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]

👉🏻그리디는 가장 큰 것 먼저 혹은 가장 작은 것 먼저!라는 것을 기억해야 한다. 이 경우는 회의 시간이 짧을 수록 가장 많이 회의를 할 수 있기 때문에 회의 마감 시간과 시작 시간이 빠른대로 정렬을 했다.

• sort에 튜플의 요소를 key값으로 사용해 회의 끝 시간과 시작 시간이 빠른 순서로 정렬한다.

count = 1
end = schedule[0][1]
for schedule_time in schedule[1:]:
    if schedule_time[0] >= end:
        end = schedule_time[1]
        count += 1

• end를 schedule의 첫 번째 요소의 회의 마감 시간으로 정한다.
• schedule을 for문 돌리면서 end와 시작시간을 확인해 end보다 크거나 같다면 end를 schedule_time의 마감시간으로 바꿔주고 count에 1을 더해준다.

👉🏻이렇게 count를 사용해주면 1차 풀이처럼 리스트의 길이를 구하는 과정 없이 바로 출력할 수도 있다!