dev/algorithm
BOJ / 11286ė² / ģ ėź° ķ [Go][Python3]
crscnt
2020. 11. 30. 21:00
š©š»š» 문ģ
11286ė²: ģ ėź° ķ
첫째 ģ¤ģ ģ°ģ°ģ ź°ģ N(1≤N≤100,000)ģ“ ģ£¼ģ“ģ§ė¤. ė¤ģ Nź°ģ ģ¤ģė ģ°ģ°ģ ėķ ģ 볓넼 ėķė“ė ģ ģ xź° ģ£¼ģ“ģ§ė¤. ė§ģ½ xź° 0ģ“ ģėė¼ė©“ ė°°ģ“ģ xė¼ė ź°ģ ė£ė(ģ¶ź°ķė) ģ°ģ°ģ“ź³ , xź° 0
www.acmicpc.net
āš» ķģ“
šØ Go
// https://www.acmicpc.net/problem/11286
// ģė”ģ“ źø°ģ¤ģ¼ė” ė½ė ģ°ģ ģģ ķ넼 ė§ėė 문ģ
package main
import (
"bufio"
"fmt"
"math"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
var n int
fmt.Fscanln(reader, &n)
var heap Heap
heap.heapArr = make([]int, n+1)
for i := 0; i < n; i++ {
var x int
fmt.Fscanln(reader, &x)
if x == 0 {
fmt.Fprintln(writer, heap.deleteHeap())
} else {
heap.insertHeap(x)
}
}
}
type Heap struct {
heapArr []int
numOfData int
}
func (heap *Heap) deleteHeap() (delVal int) {
if heap.numOfData == 0 {
return
}
delVal = heap.heapArr[1]
lastVal := heap.heapArr[heap.numOfData]
var parentIdx = 1
var childIdx = heap.getPriorityChildIdx(parentIdx)
for childIdx != -1 {
if math.Abs(float64(lastVal)) < math.Abs(float64(heap.heapArr[childIdx])) ||
math.Abs(float64(lastVal)) == math.Abs(float64(heap.heapArr[childIdx])) && lastVal <= heap.heapArr[childIdx] {
break
}
heap.heapArr[parentIdx] = heap.heapArr[childIdx]
parentIdx = childIdx
childIdx = heap.getPriorityChildIdx(parentIdx)
}
heap.heapArr[parentIdx] = lastVal
heap.numOfData--
return
}
func (heap *Heap) getPriorityChildIdx(parentIdx int) int {
if parentIdx*2 > heap.numOfData {
return -1
} else if parentIdx*2 == heap.numOfData {
return parentIdx * 2
} else {
if math.Abs(float64(heap.heapArr[parentIdx*2])) > math.Abs(float64(heap.heapArr[parentIdx*2+1])) {
return parentIdx*2 + 1
} else if math.Abs(float64(heap.heapArr[parentIdx*2])) == math.Abs(float64(heap.heapArr[parentIdx*2+1])) {
if heap.heapArr[parentIdx*2] >= heap.heapArr[parentIdx*2+1] {
return parentIdx*2 + 1
}
}
return parentIdx * 2
}
}
func (heap *Heap) insertHeap(x int) {
heap.numOfData++
var idx = heap.numOfData
for idx != 1 {
if math.Abs(float64(x)) < math.Abs(float64(heap.heapArr[idx/2])) ||
math.Abs(float64(x)) == math.Abs(float64(heap.heapArr[idx/2])) && x <= heap.heapArr[idx/2] {
heap.heapArr[idx] = heap.heapArr[idx/2]
idx = idx / 2
} else {
break
}
}
heap.heapArr[idx] = x
}
šØ Python3
# https://www.acmicpc.net/problem/11286
# ģė”ģ“ źø°ģ¤ģ¼ė” ė½ė ģ°ģ ģģ ķ넼 ė§ėė 문ģ
import sys, heapq
if __name__ == "__main__":
n = int(sys.stdin.readline())
h = []
for i in range(n):
x = int(sys.stdin.readline())
if x == 0:
if len(h) > 0:
print(heapq.heappop(h)[1])
else:
print(0)
else:
heapq.heappush(h, (abs(x), x)) # ķķ ķģ©
728x90