[python3] 1626. Best Team With No Conflicts

풀이 일자: 23.02.02 ~ 02.06 (해설찬스)

난이도: [Medium]

분류: [DP, Sorting]

문제 내용

팀에 있는 모든 플레이어의 점수의 합을 구하는데 1가지 조건이 존재한다.

Conflict가 없도록 해야 하는데 Conflict란 어린 선수가 더 나이가 많은 선수보다 더 높은 점수를 가지고 있는 것을 의미하며 같은 나이에서는 점수와 상관없이 Conflict가 일어나지 않는다.

이를 고려해서 팀의 점수를 계산했을 때 가장 높은 점수의 합을 구하는 문제이다.

 

LIS 관련 개념 포스팅

2023.02.03 - [CS/알고리즘] - [DP] 최장 증가 부분 수열(LIS) 알고리즘 with python

 

문제 해결 흐름

1. 이 문제에 적합한 알고리즘이 어떤 게 있을까?

→ 고려해야 하는 요인이 scores와 ages 2개이긴 하지만 ages를 기준으로 scores를 정렬해서 conflict를 고려한다면 LIS(Longest Increasing Subsequence)을 조금 변형한다면 풀 수 있겠다는 생각.

 

2. 우선 ages 요소를 지우기 위해 정렬이 필요하겠다. 

→ ages를 제 1기준으로 정렬하고 이후 scores를 제 2 기준으로 정렬한다. 이는 같은 ages사이에서는 점수에 의한 conflict가 발생하지 않는다고 했기 때문에 LIS를 쓰게 편하게 하기 위해서이다.

 

3. 일반적인 LIS해결 방법으로 가자.

→ 다만 현재 구하는 것은 나올 수 있는 최대 점수이기 때문에 dp를 1이 아닌 점수로 초기화해야 한다.

또한 j를 이전 포스팅과 달리 -1로 줄여가며 check하는 것은 뒤쪽이 큰게 확실하기 때문에 뒤쪽(i의 바로 앞쪽 → index 0 )부터 비교를 해서 처리를 하는 것이다.

 

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        ans = 0
        length = len(scores);
        scoreAgePair = [[0 for i in range(2)] for j in range(length)];
        
        for i in range(length):
            scoreAgePair[i][0] = ages[i];
            scoreAgePair[i][1] = scores[i];
        scoreAgePair.sort(key=lambda x: (x[0],x[1]));

        dp = [0 for i in range(length)];
        for i in range(length):
            dp[i] = scoreAgePair[i][1];
            ans = max(ans, dp[i])

        for i in range(length):
            for j in range(i - 1, -1 ,-1):
                if scoreAgePair[i][1] >= scoreAgePair[j][1]:
                    dp[i] = max(dp[i], scoreAgePair[i][1] + dp[j]);
            ans = max(ans, dp[i]);
        
        return ans;

Time complexity =  2중 for문 사용으로 O(N^2)

Space complexity = scoreAgePair 배열 사용으로 O(N^2)

 

 

다른 해결 방식

1) Top-down 방식이 존재하나 이해하지 못해 추후 포스팅 예정..

TBD

 

2) Binary Indexed Tree (BIT) / Fenwick Tree

TBD

 

문제 링크

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

Best Team With No Conflicts - LeetCode