-
1374. [Python]강의실Python_알고리즘/Gold V 2023. 10. 30. 00:49
1. 문제
https://www.acmicpc.net/problem/1374
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 우선순위 큐
- 정렬
3. 파이썬 코드
import heapq # 인풋 N = int(input()) # 리스트 저장할 리스트 num_list = [] # 강의실 번호 N 은 필요없으므로 시작과 끝값 리스트 저장 for _ in range(N): N, S, E = map(int,input().split()) num_list.append([S,E]) # 0번 인덱스 기준으로 정렬 num_list.sort(key= lambda x:x[0]) # 정답을 출력할 리스트 answer = [] # 리스트를 순회하며 for nums in num_list: # 리스트 값이 있는 경우 if answer: # 시작 시간이 answer 에 저장된 시간보다 작은 경우 새롭게 추가 if nums[0] < answer[0]: heapq.heappush(answer,nums[1]) # 만약 크거나 같은 경우 answer에 값을 뽑고 다시 추가 else: heapq.heappop(answer) heapq.heappush(answer,nums[1]) # 리스트가 비었을 경우 끝값 추가 else: heapq.heappush(answer,nums[1]) # 길이 추가 print(len(answer))
4. 문제를 풀고난 후 생각
- 앞서 풀었던 다른 강의실 배정문제와 유형자체는 매우 흡사했다.
- 시작값과 끝나는 시간을 정렬한 후 그 정렬한 값을 기준으로 우선순위 큐에 값을 넣어가면서 값을 뽑고 추가하고 반복하는 형식으로 문제를 해결했다.
- 강의 시작 시간이 2 끝나는 시간이 14 이면 끝나는 시간 14를 먼저 우선순위 큐에 값을 넣어가며 다음 시작시간이 끝시간보다 작으면 리스트 길이를 늘려가고 같거나 작으면 리스트 값을 뽑아가며 반복문이 다 돌았을 경우 정답 리스트에 길이를 출력하면 문제를 해결할 수 있다.
5. 문제를 푸는데 도움이 되는 지식
- 우선순위 큐
- 정렬
'Python_알고리즘 > Gold V' 카테고리의 다른 글
1263. [Python]시간 관리 (1) 2023.12.21 1490. [Python]자리수로 나누기 (0) 2023.11.01 1245. [Python]농장 관리 (1) 2023.10.21 7490. [Python]0 만들기 (0) 2023.10.11 1759. [Python]암호 만들기 (0) 2023.10.09