[BaekJoon] 백준 1931번 회의실 배정

[BaekJoon] 백준 1931번 회의실 배정

 

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

 

내코드

 

처음에는 이해하기 어려워서 고민하다가 다른 분들은 어떻게 풀었는지 참고해서 풀었다.

핵심은 빨리 끝나는 순으로 정렬 후 끝나는 시간이 같다면 빨리 시작하는 순으로 정렬하는 것!

어쨌건 현재 상황에서 가장 최선의 선택(빨리 끝나는 순으로 정렬)을 한다는 점에서 그리디 알고리즘이라고 볼 수 있다.

 

코드에서 파이썬의 sort함수를 사용해 줬고, 그 안에 lamda라는 인자가 있는데 처음엔 처음 보는 lamda라서 뭔지 찾아보고 구현했다. 아래와 같이 써주면 e라는 배열을 정렬할건데, 0번째 값을 우선으로 오름차순으로 나열하고, 이후에 1번째 값을 기준으로 내림차순으로 구현한다는 의미이다.

f = sorted(e, key = lambda x : (x[0], -x[1]))

 

# BaekJoon1931.py


def solution(arr):
    answer = 0
    endTime = 0
    for i in range(len(arr)):
        # 회의가 시작하는 시간이 이전 회의가 끝나는 시간보다 늦거나 같다면 가능하니까 추가
        if endTime <= arr[i][0]:
            endTime = arr[i][1]
            answer += 1
    return answer


N = int(input())
arr = []

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

# 빨리 끝나는 순 -> 빨리 시작하는 순으로 정렬
arr.sort(key=lambda x: (x[1], x[0]))
print(solution(arr))

 

 

참고

https://covenant.tistory.com/126