2023/07/07

[EvergreenTree97]

1946 신입사원 silver 1

[EvergreenTree97]

1트 - 실패

먼저 서류로 정렬한 후, 인터뷰 점수들을 비교한다. 이 과정에서 NlogN + N^2 의 시간복잡도를 소모하게 되어 시간초과가 발생

fun main() {
    with(System.`in`.bufferedReader()) {
        val T = readLine().toInt()
        val sb = StringBuilder()
        repeat(T) { tc ->
            val N = readLine().toInt()
            val arr = Array(N) {
                val (document, interview) = readLine().split(" ").map { it.toInt() }
                Score(document, interview)
            }.sortedBy { it.document }
            var count = 1 // 서류 1등은 프리패스
            for (i in 1 until arr.size) {
                var flag = true
                for (j in 0..i) {
                    if(arr[j].interview < arr[i].interview){
                        flag = false
                    }
                }
                if(flag) count++
            }
            sb.appendLine(count)
        }
        print(sb.toString())
    }
}

data class Score(
    val document: Int,
    val interview: Int,
)

[EvergreenTree97]

2트 - 성공 (개념 참고) 정렬 + 그리디

정렬을 적용한 상태에서 각 원소들을 이중 포문으로 탐색하는 것은 어리석은 일이였다. 이미 서류 순으로 나열되어 있기 때문에, 뒤쪽 순서로 갈수록 앞의 등수보다 무조건 빨라야 살아남을 수 있다. 한번의 포문을 돌면서 매번 빠른 등수로 갱신하고, 뒤로 갈수록 그 빠른 등수보다 늦다면 탈락하는 형태로 가서 O(N)으로 끝낼 수 있게 된다.

직관적으로 보이는 대로 해결하려 하지 말자, 정렬되어 있다는 점을 떠올리면 이처럼 더 최적화 시킬 수 있는 방안을 찾아낼 수 있을 것이다.

var count = 1 // 서류 1등은 프리패스
            var min = arr[0].interview
            for (i in 1 until arr.size) {
                if(min > arr[i].interview){
                    count++
                    min = arr[i].interview
                }
            }