Daily LeetCode Challenge - 1626. Best Team With No Conflicts

Problem From.

https://leetcode.com/problems/best-team-with-no-conflicts/

오늘 문제는 scores 와 ages 배열이 주어졌을 때, 각 팀의 최고 점수를 구하는 문제였다.
최고 점수 구하기에는 제한사항이 있는데 나이가 어린 사람은 나이가 많은 사람보다 더 높은 점수를 가질 수 없다는 것이었다.

scores 배열과 ages 배열을 한데 묶고 ages 순으로 정렬한뒤 scores 순으로 정렬한다.
그 다음 정렬한 배열을 처음부터 탐색하면서 하나의 age 를 볼때 역순으로 돌아가면서 만약 그 합이 그 전 합보다 크다면 dp 에 저장하는 방식으로 하여 max score 를 구해낸다.

class Solution {
    
    private data class Player(val age: Int, val score: Int)
    
    fun bestTeamScore(scores: IntArray, ages: IntArray): Int {
        var answer = 0
        val pair = Array(scores.size){idx -> Player(ages[idx], scores[idx])}
        pair.sortWith(compareBy({ it.age },{ it.score }))
        val dp = Array(scores.size) { 0 }
        
        for(i in 0 until pair.size) {
            dp[i] = pair[i].score   
            for(j in i - 1 downTo 0) {
                if(pair[i].score < pair[j].score) continue
                dp[i] = maxOf(dp[i], dp[j] + pair[i].score)
            }
            answer = maxOf(answer, dp[i])
        }
        return answer
    }
}

위 풀이의 시간복잡도는 O(N^2) 이 된다.