1946번: 신입 사원(Kotlin)

제한사항

• 테스트 케이스의 개수 T(1 ≤ T ≤ 20)
• 지원자의 숫자 N(1 ≤ N ≤ 100,000)
• 서류 심사 순위와 면접 시험 순위가 주어진다.

문제 정리

서류심사와 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발합니다.

접근 방법

나보다 숫자가 둘다 작은 사람이 있으면 불합격

저는 처음에 서류를 등수순으로 정렬하고, 면접 순서 이전에 최소값을 구하는 방식으로 풀었습니다.

서류 등수로 정렬하게 되면 다음으로 오는 모든 참가자는 면접 순서가 이전 최소 등수보다 높지 않으면 무조건 불합격입니다.

예를 들어, 서류가 1등이고 면접이 4등이라고 생각해봅시다.

일단, 어차피 서류가 1등이라 넘어갑시다.

다음 참가자가 서류가 2등 면접이 5등이라고 생각해봅시다.

서류는 당연히 1등이 존재하므로 면접이 4등보다 높아야 합니다. 그러나, 5등은 4등보다 낮은 등수이므로 불합격입니다.

다음 참가자가 서류가 3등 면접이 3등이라고 생각해봅시다.

서류는 당연히 앞에 사람이 존재하므로, 면접이 4등보다 높아야 합니다. 현재 참가자는 3등이므로 합격이다. 이제 면접 기준은 3등으로 바뀝니다. 3등보다 등수가 높지 않으면 불합격입니다.

이 방법의 시간복잡도는 O(T * NlogN)이 됩니다.

그러나, https://www.acmicpc.net/source/45907289 이 링크의 답을 보면 정렬이 필요가 없음을 알 수 있습니다.

배열의 인덱스를 서류의 등수, 배열의 값을 면접의 등수로 설정하면 정렬 필요 없이 인덱스 순서로 접근하게 되면 자연스럽게 서류의 등수 순서대로 접근이 가능합니다. 시간복잡도는 정렬이 사라지므로 O(T * N)이 됩니다.

애초에 문제에서 ‘동석차 없이 결정된다’가 힌트였습니다.

복잡도

시간복잡도 : O(T * N)

공간복잡도 : O(N)

코드

[kotlin]

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

// <https://www.acmicpc.net/source/45907289> 코드 참조해서 정렬을 제거한 코드
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var testCaseCnt = readLine().toInt()
    val output = StringBuilder()

    repeat(testCaseCnt) {
        val n = readLine().toInt()
        val scores = IntArray(n)
        var successCnt = 1

        repeat(n) {
            val (idx, value) = readLine().split(" ").map { it.toInt() - 1 }
            scores[idx] = value
        }

        var minInterviewRank = scores[0]
        for (i in scores.indices) {
            if (scores[i] >= minInterviewRank) {
                continue
            }
            minInterviewRank = scores[i]
            successCnt++
        }
        output.append(successCnt).append("\\n")
    }

    println(output)
}