[Kotlin] BOJ1713 후보 추천하기

정렬 우선순위를 세워서 풀었던 문제

 

PriorityQueue를 사용해서 해당 문제를 풀려고 했었다.
우선순위를 그냥 PriorityQueue에 위임하면 알아서 해주니까 편하게 생각했었는데
PriorityQueue는 입력 당시에 우선순위에 맞게 순서를 재정렬하지
PriorityQueue 안에 들어있는 값의 내용물을 수정해버리면
재정렬되지 않는다. 값을 수정한 값을 다시 집어넣든가 하는 방식으로 진행해야 하지
PriorityQueue 안에 있는 내용물을 함부로 바꿔선 안된다!
^^오늘의 교훈..
(heap 구현했던 것처럼 확장함수로 PQ update 구현하려고 했는데 소스코드 접근이 너무 힘들어서
그냥 ArrayList로 정렬해서 사용)

 

 

링크 : https://www.acmicpc.net/problem/1713

1713번: 후보 추천하기

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt() // (1~20) 사진틀의 개수
    val K = br.readLine().toInt() // (1~1000) 총 추천의 횟수
    val inputs = br.readLine().split(" ").map { it.toInt() } // 원소 : 1~100번 까지

    val isIn = Array(101){false}
    val picFrame = ArrayList<Student>()

    var time = 0
    for (input in inputs) {
        //이미 사진틀에 있다면
        if(isIn[input] == true){
            //추천수 올려줘야함
            picFrame.forEach { if(it.num == input) it.count++ }
        //사진틀에 없다면
        }else{
            //사진틀이 비어있다면
            if (picFrame.size < N){
                picFrame.add(Student(input,1,time++))
            }//사진틀이 꽉 찼다면
            else{
                //삭제 우선순위 : 추천수 낮은 순 > 시간이 오래된 순
                picFrame.sortWith(compareBy<Student?> { it?.count }.thenBy { it?.time })
                val out = picFrame.removeFirst()
                isIn[out.num] = false
                picFrame.add(Student(input,1,time++))
            }
            isIn[input] = true
        }
    }

    println(picFrame.map { it.num }.sorted().joinToString(" "))
}
class Student (val num :Int, 
               var count :Int,
               var time :Int)