문제풀이
- 카드 배열에서 특정 숫자보다 큰 숫자중에 가장 작은 숫자를 빠르게 구하기 위해 이분 탐색을 사용한다.
- 이미 사용한 숫자인지 아닌지 판단하기 위해 인덱스 배열을 추가하였다. (배열에 바로 접근하는 것이 아니라 인덱스 배열을 거쳐서 배열에 접근한다. arr[idxArr[idx]])
주의사항
- 주어진 숫자보다 큰 숫자가 없을 경우에는 가장 작은 숫자를 출력한다.
소요시간
40분
package 백준.Platinum.P5.p16566_카드게임
import java.io.StreamTokenizer
fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
fun readInt(): Int {
nextToken()
return nval.toInt()
}
val N = readInt()
val M = readInt()
val K = readInt()
val cards = IntArray(M)
repeat(M) { idx ->
cards[idx] = readInt()
}
cards.sort()
val cardIdxArr = IntArray(M) { it }
fun IntArray.getCardIdx(idx: Int): Int = if (this[idx] == idx) idx
else getCardIdx(this[idx]).also { this[idx] = it }
fun IntArray.higher(target: Int): Int {
val idx = binarySearch(target + 1).let { if (it >= 0) it else -(it + 1) }
return if (idx == size) higher(0)
else this[cardIdxArr.getCardIdx(idx).also { cardIdxArr[it] = (it + 1) % size }]
}
val sb = StringBuilder()
repeat(K) {
sb.appendLine(cards.higher(readInt()))
}
println(sb)
}