Greedy(3)_회의실배정(1931번)

작성일 | In

백준 1931

회의실 사용표가 있는데, 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의 수를 찾아라

주의 해야할 점 : 시작시간과 종료 시간이 일치하더라도 회의실 배정이 가능하다

아이디어

떠오르는 아이디어가 없어서. 완전 검색해보자.

자료형을 어떻게 할까. 튜플 리스트를 만들자

2시간 해보다가 안되서 다른 분들 풀이 참고했다.

이 문제를 해결하기 위해선, 시작 시간 기준으로 정렬하고, 다시 시간을 기준으로 재정렬을 해야만 한다

[참고 블로그]https://daimhada.tistory.com/38

답안

참고한 블로그 주인(다인)분의 코드를 참고하고 분석하는 것으로 이 문제를 마무리 지으려고 한다.

  1. 코드 따라 쳐보기
import sys


def greedy(meeting):
    meeting_count = 0
    start_time = 0

    for time in meeting:
        if time[0] >= start_time:
            start_time = time[1]
            meeting_count += 1
    return meeting_count


if __name__ == "__main__":
    mCount = int(sys.stdin.readline())  # 회의의 수
    meeting = []  # meeting이라는 비어있는 리스트 선언
    for i in range(mCount):
        start, end = map(int, sys.stdin.readline().split())
        meeting.append((start, end)) #이렇게 괄호를 쳐줌으로써, 튜플을 만들어준다
    # 시작 시간 기준으로 정렬
    meeting = sorted(meeting, key=lambda time: time[0])
    # 종료 시간 기준으로 정렬
    meeting = sorted(meeting, key=lambda time: time[1])
    print(greedy(meeting))

알게된 것

  1. python 사용시 main 함수 만들 때, if __name__ == "__main__":이거 복습
  2. 입출력을 빠르게 하기 위해 import sys 후 int(sys.stdin.readline()) 복습
  3. range(10)은 0부터 10미만-> 꼭 0 안써줘도 되네
  4. lambda 함수 : 람다함수는 익명 함수를 의미한다. 형식 : (lambda[매개변수]: 리턴값을 포함한 알고리즘)([매개변수 값])
    • a = (lambda foo : foo*2)(10)
    • print(a) # 20
  5. sorted 함수의 key 값으로 lambda 함수를 줬다.
    • 매개변수가 time이고, time[0]이 리턴값이다.
    • sorted의 경우 객체의 데이터 중에서 특정한 데이터를 기준으로 정렬하기 위해 key 매개변수를 사용하기도 한다.
    • 아래가 예시이다. 
      >>>students = [
   ('홍길동', 3.9, 2016303),
   ('김철수', 3.0, 2016302),
   ('최자영', 4.3, 2016301),
 ]
>>>sorted(students, key=lambda student: student[2])
[('최자영', 4.3, 2016301), ('김철수', 3.0, 2016302), ('홍길동', 3.9, 2016303)]
  6. Q) greedy 함수는 어떤 함수인가?
    • meeting_count라는 변수에,
    • 매개변수로 받은 튜플을 뽑아서
    • 첫 시간이 start_time보다 크면
    • start_time에 튜플이 끝나는 시간을 넣고
    • meeting_count를 일 증가시킨 뒤 이 값을 리턴해준다.

참고자료

[1931 문제 해결방안 블로그]https://daimhada.tistory.com/38 [sys.stdin.readline()]https://dailyheumsi.tistory.com/32 [lambda 함수]https://victorydntmd.tistory.com/239 [sorted 함수]http://cigiko.cafe24.com/python-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0-sort%EC%99%80-sorted/

0%