πŸ“– μ΅œμ†Œ νž™

λ°±μ€€ Class3 μ΅œμ†Œ νž™ , Silver2

solved_ac[Class3] μ΅œμ†Œ νž™

문제

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

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

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

μž…λ ₯

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

좜λ ₯

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

  • 예제 μž…λ ₯ 1
9
0
12345678
1
2
0
0
0
0
32
  • 예제 좜λ ₯ 1
0
1
2
12345678
0

πŸ›  자료ꡬ쑰

고등학ꡐ μˆ˜ν•™ λ¬Έμ œμ§‘μœΌλ‘œ 따지면 ν•΄λ‹Ή λ¬Έμ œλŠ” μ‘μš© λ¬Έμ œκ°€ μ•„λ‹Œ κ°œλ… λ¬Έμ œμ— μ†ν•œλ‹€. 이 κΈ°νšŒμ— Heap에 λŒ€ν•˜μ—¬ λ‹€μ‹œ ν•œ 번 곡뢀할 수 μžˆλŠ” κΈ°νšŒκ°€ λ˜μ—ˆλ‹€.

Heap은 μ–΄λ””μ—μ„œ ν™œμš©λ  수 μžˆμ„κΉŒ?

  • μš°μ„ μˆœμœ„ 큐

Heap은 기본적으둜 μš°μ„ μˆœμœ„ 큐λ₯Ό μœ„ν•΄ λ§Œλ“€μ–΄μ§„ μžλ£Œκ΅¬μ‘°μ΄λ‹€. λ”°λΌμ„œ ν›—λ‚  μš°μ„ μˆœμœ„ 큐λ₯Ό ν™œμš©ν•˜λŠ” λ¬Έμ œμ—μ„œ μ‹œκ°„λ³΅μž‘λ„λ₯Ό 쀄이기 μœ„ν•˜μ—¬ μš”κΈ΄ν•˜κ²Œ μ‚¬μš©λ  것이닀.

  • Why?

κ·Έλ ‡λ‹€λ©΄ μ™œ Heap이 배열보닀 μš°μ„ μˆœμœ„ 큐 κ΅¬ν˜„μ— μœ λ¦¬ν• κΉŒ?

스크란샷 2022-07-07 α„‹α…©α„Œα…₯ᆫ 11 52 43

μœ„μ˜ ν‘œλ₯Ό 참고해보면 Heap은 μ‚½μž…/μ‚­μ œκ°€ O(logn)이닀. κ·ΈλŸ¬λ‚˜ 배열은 μ΅œμ•…μ˜ 경우 O(n)의 μ‹œκ°„λ³΅μž‘λ„κ°€ 걸리기 λ•Œλ¬Έμ—

μš°μ„ μˆœμœ„ 큐λ₯Ό κ΅¬ν˜„ν•  λ•Œ Heap을 μ„ νƒν•˜λŠ” 것이 μ•„λ‹κΉŒ μ‹Άλ‹€.

πŸ‘¨πŸ»β€πŸ’» CODE

import sys
import heapq as h

input = sys.stdin.readline
test_case = int(input())

heap = []
for _ in range(test_case):
    command = int(input())

    if command > 0:
        h.heappush(heap,command)
    
    if command == 0:
        if not heap:
            print(0)
        else:
            print(h.heappop(heap))

Β© 2022. All rights reserved.

Powered by Hydejack v9.1.6