한 개의 회의실이 있음
이를 사용하고자 하는 n개의 회의들에 대하여 각 회의가 겹치지 않게 하면서
회의실을 사용할 수 있는 최대수의 회의를 찾는 프로그램 작성
회의는 한번 시작하면 중간에 중 단될 수 없음
한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있음
첫째 줄에 회의의 수 n이 주어짐
둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어짐: 공백을 사이에 두고 회의의 시작시간과 끝나는 시간
입력예시)
5
1 4
2 3
3 5
4 6
5 7
출력예시)
3
내가 쓴 코드
import sys
sys.stdin = open("input.txt")
#가능한 회의의 최대 갯수!!를 찾는것
#입력받기: 시작시간과 끝나는 시간 하나의 리스트로 담아 모든 쌍을 전체 리스트에 담기
N = int(input())
times = []
for _ in range(N):
times.append(list(map(int, input().split())))
#가능한 회의의 최대 갯수 찾는 함수 find_max_cnt
def find_max_cnt(times):
last_end = times[0][1]
cnt = 1
for start, end in times:
if start >= last_end:
cnt += 1
last_end = end
return cnt
#종료 시간을 기준으로 오름차순 정렬, 종료시간 같은 경우 시작시간 두번째 기준으로 정렬
times.sort(key = lambda x: (x[1],x[0]))
#최댓값찾고 출력
result = find_max_cnt(times)
print(result)
모범답안
import sys
n = int(input())
meeting = []
for i in range(n):
a,b = map(int, input().split())
meeting.append((a,b))
meeting.sort(key = lambda x: (x[1],x[0]))
et = 0
cnt = 0
for x,y in meeting:
if x >= et:
et = y
cnt += 1
print(cnt)
느낀점
1. 리스트가 담긴 리스트를 .sort()하면 기본적으로 원소 리스트의 첫번째 원소를 기준으로 sort됨
정렬 기준은 sort함수의 key매개변수를 이용해 변경 할 수 있음
ex) 원소리스트의 두 번재 요소를 기준으로 정렬하고싶다면?
.sort(key = lambda x: x[1])
2. 그리디 알고리즘이 성립하려면..
매 선택이 이후 선택에 긍정적으로 기여할 수 있는가?
- 매 선택이 이후 단계의 선택 가능성을 최대화 하는지
- 매 선택이 남은 문제의 크기를 줄이는 선택인지
3. 문제 해결의 원리를 명확히 이해하고 적용하는 습관!!
매 순간의 선택 중 최적의 선택을 생각 할 때, 이 선택이 남은 문제의 최적해에 어떻게 기여하는지를 중심으로 생각
4. 보통의 그리디 문제는 "정렬" 과 동반!
정렬 한 후(방식과 기준 선택이 중요) 골라나가는 것이 그리디의 기본
5. 튜플이 리스트보다 좋은점?
- 메모리를 적게 사용, 조금 더 빠르게 처리
- 고정된 속성의 집합을 표현할 때 적합 (예를들어 (시작 시간, 종료 시간))
- 불변성으로 인한 안전성
다시 풀어보기
import sys
sys.stdin = open("input.txt", 'rt')
# 입력 받아서 times 리스트에 (시작시간, 종료시간) 형태로 넣기
n = int(input())
times = []
for _ in range(n):
start, end = map(int, input().split())
times.append((start, end))
# 종료시간이 빠른 순서대로 (같을 경우 시작시간 빠른 순서) 정렬
times.sort(key = lambda x: (x[1], x[0]))
cnt = 0
last_end = 0
for start , end in times:
if start >= last_end:
cnt += 1
last_end = end
print(cnt)