문제
https://www.acmicpc.net/problem/1966
풀이(18분)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val sb = StringBuilder()
var st: StringTokenizer
var T = br.readLine().toInt()
while (T-- > 0) {
st = StringTokenizer(br.readLine())
val N = st.nextToken().toInt()
val num = st.nextToken().toInt()
val pq = PriorityQueue<Node>()
val q = LinkedList<Node>()
st = StringTokenizer(br.readLine())
for (i in 1..N) {
val temp = st.nextToken().toInt()
var n = Node(false, temp)
if (i - 1 == num) {
n.flag = true
}
pq.add(n)
q.add(n)
}
var max = pq.poll()
var cnt = 0
while (true) {
var temp = q.poll()
if (temp.priority == max.priority) {
cnt++
max = pq.poll()
if (temp.flag) {
sb.append(cnt).append("\n")
break
}
} else {
q.add(temp)
}
}
}
println(sb)
}
class Node(
var flag: Boolean,
val priority: Int
) : Comparable<Node> {
override fun compareTo(other: Node): Int {
return other.priority - this.priority
}
}
문제 풀이 전략
우선순위 큐를 사용해 현재 최고 우선순위를 빠르게 찾고,
큐에서 문서를 하나씩 꺼내며 해당 우선순위와 일치할 때 출력 순서를 증가시켰다.
특정 문서를 추적하기 위해 flag가 포함된 Node 클래스를 사용했다.
'문제 풀이 > 백준' 카테고리의 다른 글
[백준] 4779번. 칸토어 집합(Kotlin) (0) | 2025.10.16 |
---|---|
[백준] 1913번. 달팽이(Kotlin) (0) | 2025.10.15 |
[백준] 17490번. 일감호에 다리 놓기(JAVA) (0) | 2025.10.12 |
[백준] 9421번. 소수 상근수(JAVA) (0) | 2025.10.12 |
[백준] 18115번. 카드 놓기(JAVA) (0) | 2025.10.11 |