[백준/BOJ] 1946번: 신입 사원

문제

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

1946번: 신입 사원

해설

문제에서 핵심 문장은 "어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다."이다.

즉, 두 성적이 모두 다른 지원자보다 떨어진다면, 그 사람은 면접에서 떨어지게 된다.

문제의 예시 중 첫 번째 테스트케이스를 보자.

(3, 2), (1, 4), (4, 1), (2, 3), (5, 5)가 있다. 이를 서류 결과 성적순으로 정렬해보면 다음과 같다.

2번 참가자는 1번 참가자보다 서류 결과 성적이 떨어지지만, 면접 결과는 높다. 즉, 선발될 수 있다는 뜻이다.3번 참가자 또한 2번 참가자보다 서류 결과 성적은 떨어지지만, 면접 결과가 높으므로 선발될 수 있다.하지만 5번 참가자는 서류 결과와 면접 결과 성적 둘 다 4번 참가자에 비해 높은 것이 없다. 즉, 선발될 수 없다는 뜻이다.

 

이를 구현하는 방법으로는 그리디 알고리즘을 사용하면 된다.우선순위 큐에 값을 넣어 서류 결과 성적 순으로 정렬한 후, 면접 결과를 그 전 참가자와 비교하면 되는 간단한 문제이다.

코드

import java.util.*

private  val pq = PriorityQueue<Info>()

data class Info(val reviewRank: Int, val interviewRank: Int): Comparable<Info> {
    override fun compareTo(other: Info): Int = reviewRank - other.reviewRank
}

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()
    repeat(testCase) {
        pq.clear()
        val applicantCnt = readLine().toInt()


        repeat(applicantCnt) {
            val (reviewRank, interviewRank) = readLine().split(" ").map { it.toInt() }
            pq.add(Info(reviewRank, interviewRank))
        }

        val ans = pass(applicantCnt)
        println(ans)
    }
}

private fun pass(n: Int): Int {
    var cnt = 1
    var curStandard = pq.poll().interviewRank
    for(i in 1 until n) {
        val curApplicant = pq.poll()
        val applicantInterviewRank = curApplicant.interviewRank

        if(curStandard > applicantInterviewRank) {
            cnt++
            curStandard = applicantInterviewRank
        }
    }

    return cnt
}