[백준] 1946번 신입 사원(그리디)[Kotlin - 코틀린]

백준 1946번 문제입니다. (solved.ac) 기준 실버 1 문제입니다.

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

1946번: 신입 사원

문제

문제 접근

지원자들은 서류심사 성적과 면접시험 성적 중 어느 하나라도 다른 지원자들보다 떨어지지 않는 경우만 선발이되게 됩니다.

문제 설명은 성적을 기준으로 설명하였으나 입력값은 순위가 입력됩니다.(입력값도 성적인 줄 알고 한참을 고생했네요...)

Pair을 사용하여 first에는 서류심사의 순위, second에는 면접 심사의 순위가 담기게 되며 순위이기 때문에 1위부터 n위까지 동석차는 없이 결정된다고 합니다.

우선 first의 값인 서류심사 순위를 기준으로 오름차순 정렬을 해준 뒤 second값인 면접 순위를 비교하며 지원자들을 선발합니다.

현재 뽑인 지원자들중 제일 낮은 순위를 담을 maxRank변수를 만들어주고 이 값을 갱신해가며 지원자들을 선발합니다.

 

예제 입력 1번의 첫 번째 테스트 케이스를 기준으로 예시를 들어보겠습니다.

5명의 지원자가 있고 순위가 각각 (3 2) (1 4) (4 1) (2 3) (5 4) 와 같이 구성되어있습니다. 
이를 서류심사 순위를 기준으로 정렬하면 (1 4) (2 3) (3 2) (4 1) (5 5)로 정렬이 됩니다.

첫 번째 지원자인 (1 4) 순위의 지원자는 이미 서류심사의 순위가 최상위 이기때문에 반드시 뽑히게 되고 이 지원자가 뽑혔기 때문에 maxRank는 4가 됩니다. 

두 번째 지원자인 (2 3) 순위의 지원자는 maxRank인 4보다 면접 순위가 3으로 높기 때문에 선발이되고 maxRank는 3으로 갱신됩니다.

세 번째 지원자인 (3 2) 순위의 지원자도 마찬가지로 maxRank보다 면접 순위가 높기 때문에 선발 후 maxRank는 2로 갱신됩니다.

네 번째 지원자인 (4 1) 순위의 지원자도 마찬가지로 maxRank보다 면접 순위가 높기 때문에 선발 후 maxRank는 1로 갱신됩니다.

마지막 지원자인 (5 5) 순위의 지원자는 maxRank인 1보다 면접 순위가 낮으므로 선발이 불가능합니다.

따라서 예제 입력 1번에서 1번 테스트 케이스에서 신입사원이 될 수 있는 최대 인원수는 4명입니다.

정답 코드

fun main(){

    // 테스트 케이스만큼 반복
    val t = readln().toInt()
    repeat(t){

        // 서류심사 순위, 면접 순위순으로 저장.
        val gradeList = mutableListOf<Pair<Int,Int>>()
        // 지원자의 수
        val n = readln().toInt()
        // 뽑을 수 있는 최대 지원자의 수
        var ans = 0
        // 현재까지 뽑힌 지원자의 면접 순위중 가장 낮은 순위를 담을 변수
        var maxRank = Int.MAX_VALUE

        // 지원자의 성적순위를 저장
        repeat(n){
            val rankData = readln().split(" ").map { it.toInt() }
            gradeList.add(Pair(rankData[0],rankData[1]))
        }

        // 지원자의 서류심사 순위로 오름차순 정렬
        gradeList.sortBy{it.first}

        gradeList.forEachIndexed { index, curApplicant ->

            // 지원자들의 서류심사 순위로 이미 정렬이 되었기 때문에
            // 현재 뽑힌 지원자들의 면접 순위의 가장 낮은 등수 보다 작다면 뽑힐 수 있다는 뜻
            if (maxRank > curApplicant.second){
                maxRank = curApplicant.second
                ans++
            }

        }

        println(ans)
        gradeList.clear()
    }
}