μ΄λ² νμ΄μ ν΅μ¬ ννΈλ μ°μ μμ ν μ λλ€. μ°μ μμ νλ₯Ό μ΄μ©ν΄ λ°±μ€ 11000λ² (κ°μμ€ λ°°μ ) λ¬Έμ λ₯Ό νμ΄μ¬μΌλ‘ νμ΄ λ³΄λλ‘ νκ² μ΅λλ€. ν΄λΉ μλ£κ΅¬μ‘°λ₯Ό μ μ¬μ©νμλ©΄ λ¬Έμ κ° μ¬μμ§λ κ²μ λλΌμ€ μ μμ κ² μ λλ€.
μ΄λ² κΈμμ μμλ³Ό λ΄μ©
- λ¬Έμ μ€λͺ
- λ¬Έμ μ ν΅μ¬ μμ΄λμ΄
- λ¬Έμ νμ΄
λ¬Έμ μ€λͺ
11000λ²κ³Ό κ°μ κ²½μ° λ¬Έμ μ€λͺ μ체μ μ€ν΄μ μμ§κ° μμ΅λλ€. μκ°μ μ²μ λ§μ€ν° κΉμ’ ν μ μλμ΄ μλλΌ μκ°μ μ² κ΄λ¦¬μ κΉμ’ ν μ μλμ΄ λ μλ§λ νν κ°μ΅λλ€. μ¦ μ΄λ² λ¬Έμ λ μκ°μ μ²μ κ΄λ¦¬ν΄μ κ°μμ€μ μ¬λ°λ₯΄κ² λ°°μΉνλ κ²μ μꡬν©λλ€. κ°μμ μκ°μ΄ μ£Όμ΄μ§λ©΄ ν΄λΉ κ°μμ νμν κ°μμ€μ λ°°μΉν΄μ£Όλ κ² μ λλ€. μ΄λ κ°μ₯ μ κ² κ°μμ€μ μ¬μ©ν μ μλ λ°©λ²μ λ¬»κ³ μμ΅λλ€.
λ¬Έμ μ ν΅μ¬ μμ΄λμ΄
ν΅μ¬ μμ΄λμ΄λ κ°μκ° κ²ΉμΉλμ§ νμΈνλ κ² μ λλ€. κ°μμ€μ΄ μΆκ°λ‘ νμν μν©μ λ¨ ν κ°μ§ λ°μ μμ΅λλ€. λ°λ‘ μ΄λ€ ν κ°μκ° λλμ§ μμλλ° λ€λ₯Έ κ°μκ° μμνλ κ² μ΄μ£ . μ΄λ₯Ό κ΄λ¦¬νκΈ° μν΄μλ μ°μ μμ νλ₯Ό νμ©νλ©΄ κ°λ¨ν ν΄κ²°ν μ μμ΅λλ€. μ°μ μμ νλ νμ ννλ₯Ό κ°μ§κ³ μμ§λ§ μμ λ Έλλ€μ΄ μ λ ¬μ΄ λμ΄ μλ νλ₯Ό λ»νλλ°μ. νμ νΈμ¬λ₯Ό νλ©΄ λ€μ μμ΄λ κ²μ΄ μλλΌ μ λ ¬μ΄ λμ΄μ κ°μ΄ μ μ₯λ©λλ€. μ°μ μμ νλ₯Ό μ¬μ©νλ©΄ λλλ μκ°μ΄ κ°μ₯ λΉ λ₯Έ κ°μλΆν° popν μ μκ² λ©λλ€. μκ³ λ¦¬μ¦μ μμλ‘ νννμλ©΄
- κ°μ 리μ€νΈλ₯Ό μ λ ¬νλ€.
- 첫 λ²μ§Έ κ°μκ° λλλ μκ°μ μ°μ μμ νμ μΆκ°νλ€.
- κ°μ 리μ€νΈμ 1λ²μ§Έ μΈλ±μ€λΆν° λ§μ§λ§κΉμ§ λ°λ³΅λ¬Έμ μ€ννλ€
- μ°μ μμ νμ 첫 λ²μ§Έ μΈλ±μ€μ μ κ·Όνλ€ (νμ λλλ μκ°μ΄ κ°μ₯ λΉ λ₯Έ μ)
- λ§μ½ κ°μμ μμμκ°μ΄ μ°μ μμ νμ 첫 λ²μ§Έ μΈλ±μ€λ³΄λ€ μλ€λ©΄ ν΄λΉ κ°μμ λλλ μκ°μ μ°μ μμ νμ μΆκ°νλ€.
- μλλΌλ©΄ μ°μ μμ νμ 첫 λ²μ§Έ μΈλ±μ€λ₯Ό pop ν ν ν΄λΉ κ°μμ λλλ μκ°μ μ°μ μμ νμ μΆκ°νλ€.
μμ κ³Όμ μ μ λΆ κ±°μΉκ² λλ©΄ μ°μ μμ νμ ν¬κΈ°λ νμν κ°μμ€ κ°μλ§νΌμ΄ λ©λλ€. λ°λΌμ μ°μ μμ νμ ν¬κΈ°λ₯Ό μΆλ ₯νλ©΄ μ λ΅μ μΆλ ₯ν μ μμ΅λλ€. λ μμΈν μ΄ν΄λ μλμ μ½λλ₯Ό μ°Έμ‘°ν΄μ£ΌμΈμ
λ¬Έμ νμ΄
import heapq
n = int(input())
lecture_list = [list(map(int, input().split())) for _ in range(n)]
lecture_list.sort()
lecture_queue = []
heapq.heappush(lecture_queue, lecture_list[0][1])
for i in range(1, n):
if lecture_list[i][0] < lecture_queue[0]:
heapq.heappush(lecture_queue, lecture_list[i][1])
else:
heapq.heappop(lecture_queue)
heapq.heappush(lecture_queue, lecture_list[i][1])
print(len(lecture_queue))
λ§λ¬΄λ¦¬νλ©΄μ
μ΄μμΌλ‘ 11000λ² λ¬Έμ νμ΄λ₯Ό λ§μΉλλ‘ νκ² μ΅λλ€. κ²°κ΅ μκ³ λ¦¬μ¦ λ¬Έμ λ μλ£κ΅¬μ‘°λ₯Ό κΈ°λ°μΌλ‘ μκ°ν΄μΌ ν©λλ€. λ©λͺ¨λ¦¬ μμμ μλνκΈ° λλ¬Έμ μλ£κ΅¬μ‘°λ₯Ό λ²μ΄λ μ μκΈ° λλ¬Έμ΄μ£ . λ°λΌμ μ μ°νκ² μλ£κ΅¬μ‘°λ₯Ό νμ©ν μ μλ λ₯λ ₯μ΄ μκ³ λ¦¬μ¦ νμ΄μμ μ€μνκ² μμ©νλ κ² κ°μ΅λλ€. κ·Έλ° μλ―Έμμ λ€μμλ νμ΄μ¬μ heapq μ¦ μ°μ μμ νμ κ°μ μλ£κ΅¬μ‘°λ€μ λ€λ£¨μ΄ 보λλ‘ νκ² μ΅λλ€. λΆμ‘±ν κΈ μ½μ΄μ£Όμ μ κ°μ¬ν©λλ€.
'Algorithm > Python' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
Union find μκ³ λ¦¬μ¦ - Python (0) | 2021.09.29 |
---|---|
ν¬λ£¨μ€μΉΌ μκ³ λ¦¬μ¦ - Python (0) | 2021.09.28 |