[Kotlin] 백준(BOJ) 1946 신입 사원

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

문제 전문은 아래 버튼을 눌러 확인하실 수 있습니다.

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

예제 입출력

알고리즘 분류

그리디 알고리즘

정렬

문제 해설

문제의 설명이 약간 난해할 수 있는데 때문에 문제에서도 핵심 내용을 다음 한 문장으로 정리해주고 있다.

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

 

이에 따라 단순히 생각했을 때 어떤 지원자가 합격인지 판단하려면, 성적 중 하나가 다른 지원자보다 떨어지지만 않으면 되므로, 단순히 그러한지 대조해보는 $O(N^2)$ 방법으로 해결할 수도 있겠으나, 그리디 알고리즘으로 해결할 수 있었다. (아마 문제 정답률과 입력 크기를 고려해봤을 때 해당 방법으로 해결하면 시간초과가 발생할 확률이 높아보인다.)

 

대표적인 그리디 알고리즘의 유형 중 하나인 활동 선택(회의시간 짜기, 시간표짜기 등)문제 처럼 고려해야할 지표가 두 가지 이므로,

우선 1가지 성적을 기준점으로 정렬해야 한다(서류, 면접 순으로 입력되므로 서류 성적을 기준으로 정렬하는 것이 좋아 보인다)

 

이렇게 함으로써 정렬된 순서대로만 고려하면 우선 서류 성적 1등은 자동적으로 합격시킬 수 있고, 순차적으로 합불을 고려한다면

이번에 고려하는 지원자의 서류 성적이 이전에 합격한 지원자의 서류 성적보다 낮으므로, 결국 면접 성적만 고려해서 해당 지원자의 합불을 결정할 수 있다.

 

결론적으로, 서류 성적으로 정렬 한 후, 단순히 면접 성적이 지금까지 합격한 지원자의 면접 성적 중 가장 낮은 면접 성적보다 낮다면 불합격이고 그렇지 않다면 합격이라고 결정할 수 있겠다.

 

주의할 점은 문제에는 "성적"이라고 설명되어있기 때문에 정렬할 때 내림차순(높은 성적)으로 정렬해야겠다고 생각할 수도 있는데, 입력 부분을 읽어보면 사실 "순위"가 입력된다. 때문에 오름차순으로 정리해야 높은 성적 순서대로 비교할 수 있다.

소스코드

fun main() {
    // 케이스 수
    val case = readln().toInt()
    repeat(case) {
        val applicants = readln().toInt()
        var passApplicants = 0
        // 지원자 수
        val applicantsScores = readApplicantsScores(applicants)
        // 서류 순위를 기준으로 정렬
        val sortedScores = applicantsScores.sortedBy { it.first }
        // 면접 순위 최소 컷
        // 서류 1등 지원자는 반드시 합격해야 하므로 등수 최댓값 + 1로 초기화
        var minInterviewScore = 100_001
        sortedScores.forEach {
            if (it.second < minInterviewScore) {
                passApplicants++
                minInterviewScore = it.second
            }
        }
        println(passApplicants)
    }
}

fun readApplicantsScores(applicants: Int): List<Pair<Int, Int>> {
    val applicantsScores = mutableListOf<Pair<Int,Int>>()
    repeat(applicants) {
        val (paperScore, interviewScore) = readln().split(" ").map { it.toInt() }
        applicantsScores.add(paperScore to interviewScore)
    }
    return applicantsScores
}

 

시간 복잡도

시간 복잡도는 정렬에 $O(NlogN)$, 적절성 검사에 $O(N)$ 이므로 $O(NlogN)$ 으로 예상된다.