[python]백준_1931 : 회의실 배정

Choco Ham·2022년 9월 2일

algorithm python 백준

algorithm

목록 보기

4/6

🚗현대인을 위한 3줄요약.

sort 메소드의 key값으로 함수를 대입할 수 있다. lambda 표현식을 사용하여 함수를 짧고 간결하게 선언할 수 있다.

📌전체코드

문제 링크 : https://www.acmicpc.net/problem/1931

우선 전체 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n = int(input())
meeting = []
for _ in range(n):
    meeting.append(list(map(int, input().split()))) # 문제의 입력형식에 맞게 map과 list를 사용
# sort를 진행할 때 sort의 key로 lambda 함수를 대입하여 정렬의 기준을 세운다.
# x에 대하여 마지막 index의 값을 기준으로 우선 정렬 후 첫번째 index 값을 기준으로 또다시 정렬한다.
meeting.sort(key = lambda x : (x[1], x[0]))

tail = 0    # 회의 종료시간을 대표하는 변수
count = 0   # 회의를 진행할 수 있는 횟수
for i in meeting:
    if i[0] >= tail:    # 회의 시작시간(i[0]이 tail(이전 회의의 종료시간)보다 클 경우 명령 실행)
        count += 1	# 회의 가능횟수 + 1
        tail = i[1] # 회의 종료시간 업데이트
print(count)

해당 코드에서 면밀히 살펴볼 부분은 다음과 같다.

split : 문자열을 쪼갤때 사용한다.
sort(key = ~ ) : key를 기준으로 정렬한다.
lambda 표현식 : 함수의 선언 방식.

각 키워드가 포함된 문단별로 나눠서 분석해보자

👉split

split은 문자열을 쪼갤때 사용되는 메소드이다. 입력받는 파라메터에 따라 문자열을 쪼개는 기준이 달라진다. 아무것도 입력하지 않을 경우 공백을 기준으로 쪼갠다.

str = "I am Groot"
print(str.split())

str2 = "abc,def,ghi,jkl"
print(str2.split(','))

# 실행 결과 : ['I', 'am', 'Groot']
#			 ['abc', 'def', 'ghi', 'jkl']

map 함수는 2개 이상의 변수에 대해 함수를 적용할 때 사용된다.

x, y = map(int, ['123', '456'])
print(type(x), x)

# 실행 결과 : <class 'int'> 123

여기서 list를 생성/제어하는 list함수와 함께 map, split을 함께 사용하면 문제에서 요구하는 형식에 맞게 값을 입력할 수 있다.

for _ in range(n):
    meeting.append(list(map(int, input().split())))
    
# 실행 결과 : [[0, 3], [1, 5], [7, 2], ... ]

백준에서는 이런 형식의 문제가 많이 출제되니 알아두는게 좋다.

👉lambda 표현식

lambda 표현식은 아주 간단한 익명 함수를 선언할때 사용되는 방법이다. 사용법은 다음과 같다.

plus_ten = lambda x: x + 10
print(plus_ten(1))
    
# 실행 결과 : 11

lambda 앞에 매개변수를 선언한 후 해당 매개변수를 : 뒤에서 제어하는 방식이다.
lambda 함수는 또한 다음과 같은 특징을 가진다.

lambda 함수는 인수로써 쓰일 수 있다.
lambda 함수 내에서 변수를 선언할 수 없다.
외부에서 선언된 변수는 lambda식 내에서 쓸 수 있다.

이중에서 주목해야할 특징은 lambda 함수가 인수로써 쓰일 수 있다는 점이다. 이는 sort 메소드의 key값으로 lambda 함수가 쓰일 수 있음을 뜻한다.

👉sort(key = ~ )

지난번에 소개했던 sort 메소드의 또다른 특징은 특정 key값을 기준으로 정렬을 진행할 수 있다는 것이다.

arr = ['kbcde', 'abc', 'u', 'mbcdefg', 'jbcd']

# 실행 결과 : ['u', 'abc', 'jbcd', 'kbcde', 'mbcdefg']

위의 예제에서 정렬의 기준을 len. 즉 문자열의 길이로 지정했기 때문에 알파벳이 아닌 문자열의 길이를 기준으로 정렬되었다.
만약 함수가 key값으로 쓰인다면 함수의 조건이 정렬 기준이 된다.

# x에 대하여 마지막 index의 값을 기준으로 우선 정렬 후 첫번째 
# index 값을 기준으로 또다시 정렬한다.
meeting.sort(key = lambda x : (x[1], x[0]))

위와같이 meeting 리스트를 회의 종료시간으로 한번, 회의 시작시간으로 또 한번 정렬을 마쳤다면 남은건 회의의 진행 가능 횟수를 세는것으로 마무리 된다.

tail = 0    # 회의 종료시간을 대표하는 변수
count = 0   # 회의를 진행할 수 있는 횟수
for i in meeting:
	# 회의 시작시간(i[0]이 tail(이전 회의의 종료시간)보다 클 경우 명령 실행)
    if i[0] >= tail:
        count += 1	# 회의 가능횟수 + 1
        tail = i[1] # 회의 종료시간 업데이트
print(count)

📌다른 방법

import sys

N = int(sys.stdin.readline())

time = [[0]*2 for _ in range(N)]
for i in range(N):
    s, e = map(int, sys.stdin.readline().split())
    time[i][0] = s
    time[i][1] = e

time.sort(key = lambda x: (x[1], x[0]))

cnt = 1
end_time = time[0][1]
for i in range(1, N):
    if time[i][0] >= end_time:
        cnt += 1
        end_time = time[i][1]

print(cnt)
                
# 출처 : https://suri78.tistory.com/26