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

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

 

 

 

[난이도] Silver2
[유형] 힙

[풀이]
Heap

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val pq = PriorityQueue<Int>{a,b->b.compareTo(a)}
    var N = readLine().toInt()
    repeat(N){
        var v = readLine().toInt()
        when{
            v>0 -> pq.add(v)
            pq.isEmpty() -> println(0)
            else -> println(pq.poll())
        }
    }
}

 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/11279.cpp

저작자표시

'Problem-Solving > BOJ' 카테고리의 다른 글

[BOJ/백준][Silver3] 15652 : N과 M (4) (Kotlin)  (0) 2021.08.06
[BOJ/백준][Silver3] 15650 : N과 M (2) (Kotlin)  (0) 2021.08.06
[BOJ/백준][Silver2] 18870 : 좌표 압축 (C++)  (0) 2021.07.25
[BOJ/백준][Silver5] 17626 : Four Squares (C++)  (0) 2021.07.25
[BOJ/백준][Silver4] 17219 : 비밀번호 찾기 (Kotlin)  (0) 2021.07.25

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

 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

 

 

 

[난이도] Silver1
[유형] 우선순위큐

[풀이]
maxHeap, minHeap 두가지를 이용하면 답을 구할 수 있습니다.
pair(abs(x),x) 를 저장하는 Heap 한개로도 문제를 풀수 있습니다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.abs
const val mxN = 1 shl 31
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val minHeap = PriorityQueue<Int>()
    val maxHeap = PriorityQueue<Int>{a,b->b.compareTo(a)}
    repeat(readLine().toInt()){
        val v = readLine().toInt()
        when{
            v==0->{
                var ret=0
                if(!minHeap.isEmpty() || !maxHeap.isEmpty()){
                    ret = when {
                        minHeap.isEmpty() -> maxHeap.poll()
                        maxHeap.isEmpty() -> minHeap.poll()
                        else -> if(abs(minHeap.peek()) < abs(maxHeap.peek())) minHeap.poll() else maxHeap.poll()
                    }
                }
                println(ret)
            }
            v<0 -> maxHeap.add(v)
            else -> minHeap.add(v)
        }
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/11286.cpp

저작자표시

'Problem-Solving > BOJ' 카테고리의 다른 글

[BOJ/백준][Silver1] 1629 : 곱셈 (C++)  (0) 2021.07.25
[BOJ/백준][Silver3] 11659 : 구간 합 구하기4 (Kotlin)  (0) 2021.07.25
[BOJ/백준][Silver3] 9375 : 패션왕 신해빈 (Kotlin)  (0) 2021.07.18
[BOJ/백준][Silver1] 6064 : 카잉 달력 (C++)  (0) 2021.07.18
[BOJ/백준][Silver2] 5525 : IOIOI (C++)  (0) 2021.07.18

+ Recent posts

티스토리툴바