[백준] 1931 회의실 배정 (실버1) / lambda(람다) : 익명함수

문제요약

나의 코드 및 설명 (시간초과)

• n번의 회의가 주어진다면, 첫 번째로 가지는 회의의 모든 경우를 다 따진 후 최댓값을 구하는 코드를 작성하였다.
• 모든 경우를 다 따지는 거라 시간초과가 뜰 것이라 생각했는데 역시나 시간초과가 떴다. 

import sys
n = int(input())

all = []
for _ in range(n):
    all.append(list(map(int, sys.stdin.readline().split())))

for i in range(len(all)):
    ans = 1
    cnt = 1
    meeting = []
    meeting.append(all[i])
    for j in range(len(all)):
        if j == i:
            continue
        else:
            tmp_cnt = 0
            for k in range(len(meeting)):
                if meeting[k][0] < all[j][0] < meeting[k][1]\
                      or meeting[k][0] < all[j][1] < meeting[k][1]:
                    continue
                else:
                    tmp_cnt +=1
            if tmp_cnt == len(meeting):
                meeting.append(all[j])
                cnt += 1
    if cnt > ans:
        ans = cnt

print(ans)

 

다른 코드 및 설명

• time = sorted(time, key=lamda a: a[0]) \ time = sorted(time, key=lambda a: a[1]) :
  가장 많은 수의 회의를 하기 위해서는 회의가 끝나는 시각이 빨라야 한다. 따라서 먼저 시작시각을 기준으로 오름차순 정렬하고, 끝나는시각을 기준으로 오름차순을 정렬하여, 정렬된 모든 회의 시각에서 다음 회의의 시작시각이 현재 회의의 끝나는 시각보다 크거나 같다면 cnt에 1을 더한다. 

n = int(input())
time = []

for _ in range(n):
    start, end = map(int, input().split())
    time.append((start,end))

#시작 시각을 기준으로 오름차순 정렬
time = sorted(time, key=lambda a: a[0])
#끝나는 시각을 기준으로 오름차순 정렬
time = sorted(time, key=lambda a: a[1])

cnt = 1
last = time[0][1]
for i in range(1, n):
    #다음 회의 시간의 시작시각이 이전 회의의 끝나는시각보다 크거나 같다면
    if time[i][0] >= last:
        #회의 가능
        cnt += 1
        #끝나는시각을 다음 회의의 끝나는시각으로 갱신
        last = time[i][1]

print(cnt)

lambda 함수 : 익명함수

• 람다 함수는 결과 부분을 return 키워드 없이 자동으로 return 해준다.

#두 코드의 결과는 같다.
def a(x):
    return x+1
    
lambda x : x+1

• 람다 함수는 정의와 동시에 사용할 수 있다.

(lambda x : x+1)(3)
>> 4

• 하지만, 함수에 이름도 없고 저장된 변수가 없기 때문에 다시 사용할 수 는 없다.
  람다 함수도 객체이기 때문에 정의와 동시에 변수를 담을 수 있다.

func = lambda x : x+1
func(4)
>> 5

lambda 함수의 사용 예시

• sorted 함수의 경우 key위치 인자에 함수를 보내서 함수에서 지정한 결과값에 따라서 정렬을 할 수 있다.

target = ['  cat ', ' tiger ', '    dog', 'snake   ']

• 위와 같은 문자를 정렬할 때, 알파벳 순서가 아니라 앞뒤 불필요한 공백을 제외한 문자의 길이로 정렬을 하고 싶다면,
  정렬의 기준으로 사용할 값을 리턴하는 함수를 생성하여, sorted 함수에 넘겨줘야 한다.
• my_key 라는 함수를 통해, sorted 함수의 key 위치인자에 공백을 제거한 문자의 길이 순으로 정렬할 수 있다.
  하지만 my_key 라는 함수는 이번 정렬만을 위한 함수이고, 재사용할 이유가 없기 때문에 lambda 함수를 생성하여 넘겨주는 편이 더 좋다.

def my_key(string):
    return len(string.strip())
print(sorted(target, key = my_key))

###람다 함수 이용
print(sorted(target, key = lambda x : len(x.strip())))

피드백

시간 초과를 방지하기 위해 모든 회의 시각을 정렬하고 O(N)의 시간복잡도를 가질 수 있도록 문제를 해결하면 되겠구나 싶었는데 구현하기 쉽지 않았다. 회의를 가장 많이 하려면 끝나는 시각순으로 오름차순 정렬해야된다는 것이 핵심이고, 특히 lambda 함수를 이용해 sorted 함수의 key 위치인자에 접근하는 방법은 유용할 것 같으니 꼭 숙달하도록 하자.