링크 : https://www.acmicpc.net/problem/1931
- 문제
- 소요 시간 : 실패



- 설계하기(접근방법)
1. 총 회의 개수를 입력받는다
2. 1번만큼 for문을 통해 이중배열의 형태로 입력받는다
해결방법 떠올리기(실패)
해법:
1. 끝나는 시간이 빠를수록, 다음 회의를 더 많이 잡을 수 있다.
2. 끝나는 시간이 같은 회의시간이 여러개인 경우 : 1번 의 정렬을 마친 후, 시작 시간을 기준으로 오름차순 정렬한다.
Ex)
3 3
3 3
3 4 의 경우 만약
3 4
3 3
3 3 으로 정렬되어있다면 뒤의 두 개의 회의는 포함되지 않는다. 문제의 조건에 시작과 끝이 같은 경우도 포함한다고 했기 때문이다.
따라서 정렬을 할 때 람다식을 이용해 lambda x : (x[1], x[0])을 키값으로 정렬한다
여기서 x[1] 은 끝나는 시간, x[0]은 시작 시간이다.
3. 회의 개수를 count할때,
맨 처음의 회의는 항상 포함되니 cnt = 1로 선언하고 endtime은 첫 회의의 종료시간으로 해준다
처음 케이스를 처리했으니 for문을 순회할 때 range는 1부터 n까지로 설정한다.
마지막으로 카운트되었던 회의의 종료시간과 현재 for문에서 순회하고 있는 시작시간을 비교하여 후건이 같거나 크면
cnt += 1을 해주고 endtime을 후건의 종료시간으로 바꾸어준다
4. cnt를 출력한다
- 코드(출력)
import sys
input = sys.stdin.readline
n = int(input())
meetlist = []
for i in range(n):
meetlist.append(list(map(int, input().split())))
meetlist.sort(key=lambda x: (x[1], x[0]))
cnt = 1
endtime = meetlist[0][1] # 4
for i in range(1, n):
if endtime <= meetlist[i][0]:
cnt += 1
endtime = meetlist[i][1]
print(cnt)
- 얻어갈 부분

1. sys.stdin.readline 를 사용한 것과 안한 것의 시간 차이이다. 처음부터 sys를 쓰려고 하지는 말아도,
내 코드가 충분히 논리적이고 가독성이 좋았다고 생각했는데 시간이 초과된다면 적극 사용하자.
2. lambda 함수의 역할을 알게되었고, sort 함수에서 키 값으로 어떤 역할을 하는지 알게되었다.
'알고리즘(백준) > 그리디' 카테고리의 다른 글
| [알고리즘/그리디] 1946 번 : 신입 사원 - python (0) | 2023.03.02 |
|---|---|
| [알고리즘/그리디] 1439 번 : 뒤집기 - python (0) | 2023.02.24 |
| [알고리즘/그리디] 10610 번 : 30 - python (0) | 2023.02.21 |
| [알고리즘/그리디] 13305번 : 주유소 - python (0) | 2023.02.21 |
| [알고리즘/그리디] 10162번 : 전자레인지 - python (0) | 2023.02.21 |