__Python/__Algorithm

[Python] λ°±μ€€ - 11279 μ΅œλŒ€ νž™

KL_ 2022. 1. 7. 18:07

 

  λ¬Έμ œ

https://www.acmicpc.net/problem/11279

 

πŸ”Ή λ¬Έμ œ

널리 잘 μ•Œλ €μ§„ 자료ꡬ쑰 쀑 μ΅œλŒ€ νž™μ΄ μžˆλ‹€. μ΅œλŒ€ νž™μ„ μ΄μš©ν•˜μ—¬ λ‹€μŒκ³Ό 같은 연산을 μ§€μ›ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

  1. 배열에 μžμ—°μˆ˜ xλ₯Ό λ„£λŠ”λ‹€.
  2. λ°°μ—΄μ—μ„œ κ°€μž₯ 큰 κ°’을 좜λ ₯ν•˜κ³ , κ·Έ 값을 λ°°μ—΄μ—μ„œ μ œκ±°ν•œλ‹€.

ν”„λ‘œκ·Έλž¨μ€ μ²˜μŒμ— λΉ„μ–΄μžˆλŠ” λ°°μ—΄μ—μ„œ μ‹œμž‘ν•˜κ²Œ λœλ‹€.

 

πŸ”Ή μž…λ ₯

첫째 쀄에 μ—°μ‚°μ˜ 개수 N(1 ≤ N ≤ 100,000)이 μ£Όμ–΄μ§„λ‹€. λ‹€μŒ N개의 μ€„μ—λŠ” 연산에 λŒ€ν•œ 정보λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μ •μˆ˜ xκ°€ μ£Όμ–΄μ§„λ‹€. λ§Œμ•½ xκ°€ μžμ—°μˆ˜λΌλ©΄ 배열에 xλΌλŠ” 값을 λ„£λŠ”(μΆ”κ°€ν•˜λŠ”) 연산이고, xκ°€ 0이라면 λ°°μ—΄μ—μ„œ κ°€μž₯ 큰 값을 좜λ ₯ν•˜κ³  κ·Έ 값을 λ°°μ—΄μ—μ„œ μ œκ±°ν•˜λŠ” κ²½μš°μ΄λ‹€. μž…λ ₯λ˜λŠ” μžμ—°μˆ˜λŠ” 231보닀 μž‘λ‹€.

 

πŸ”Ή μΆœλ ₯

μž…λ ₯μ—μ„œ 0이 μ£Όμ–΄μ§„ 회수만큼 닡을 좜λ ₯ν•œλ‹€. λ§Œμ•½ 배열이 λΉ„μ–΄ μžˆλŠ” 경우인데 κ°€μž₯ 큰 κ°’을 좜λ ₯ν•˜λΌκ³  ν•œ κ²½μš°μ—λŠ” 0을 좜λ ₯ν•˜λ©΄ λœλ‹€.

 

  ν’€μ΄ 방법

 

πŸ”Ή μš°μ„ μˆœμœ„ 큐

πŸ”Ή νž™(heap) - heapq

πŸ”Ή μ΅œλŒ€νž™

 

  κ΅¬ν˜„ μ½”λ“œ

import sys
import heapq
N = int(sys.stdin.readline())
inputs = [int(sys.stdin.readline()) for _ in range(N)]
heap = []

for num in inputs:
    if num == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap,(-num,num))

 

  μ‹€ν–‰ κ²°κ³Ό

 

  πŸ’‘

 

 

 

 

 

 

 

 

728x90