[알고리즘] 후보 추천하기 (백준 1713번)

1713번: 후보 추천하기

 시뮬레이션 + 자료구조를 적절히 활용하는 문제이다. 우선순위 큐를 만들어서 정해놓은 큐의 최대 크기를 넘어서면 가장 우선순위가 낮은 요소부터 제거하는 원리의 문제다. 물론 문제 자체가 쉬워서 여러 풀이가 가능하지만 정렬을 활용해야한다는 점은 변함없다.

 

Solution

1. 학생마다의 추천수를 보관하는 recommendation, 사진 게시 시기를 나타내는 time
2. 우선순위 큐의 정렬 기준은 recommendation이 가장 작을 수록, time이 가장 작을 수록 앞으로 게시된다.
3. 사진 게시 시기는 반복문의 현재 index로 한다.
4. 추천 받은 학생이 queue에 없는 경우
   1. 사진을 새로 게시하는 것이므로 time을 현재 index 값으로 갱신한다.
   2. queue의 사이즈가 N이면 queue를 poll하고 제거된 학생의 추천수를 0으로 만든다
   3. queue에 현재 학생을 추가한다.
5. 추천 받은 학생이 queue에 있는 경우
   1. 추천 수가 증가했기 때문에 새로 정렬할 필요가 있으므로 학생을 queue에서 remove 후에 다시 추가한다.
6. 오름차순으로 정렬 후에 출력

import java.util.*
import kotlin.collections.ArrayList

fun solution(){

    var N = readLine()!!.toInt()
    var M = readLine()!!.toInt()

    var recommendation = IntArray(101)
    var time = IntArray(101)

    var queue = PriorityQueue<Int>(
        {o1, o2 ->
            if(recommendation[o1] == recommendation[o2])
                time[o1] - time[o2]
            else
                recommendation[o1] - recommendation[o2]
        }
    )

    var str = readLine()!!.split(" ")

    for(i in 0 until str.size)
    {
        var student = str[i].toInt()

        recommendation[student] ++

        if(!queue.contains(student))
        {
            //새로 게시됨 -> 게시 시간 갱신
            time[student] = i
            
            //사진틀 꽉참
            if(queue.size == N)
                recommendation[queue.poll()] = 0
            queue.offer(student)

        }
        //이미 게시되어있음
        else
        {
            //새로 삽입해서 다시 정렬되도록
            queue.remove(student)
            queue.offer(student)
        }
    }

    var result = ArrayList<Int>(queue)

    result.sort()

    for(a in result)
        print("$a ")
}


fun main() {
    solution()
}