[Java] LeetCode 1626. Best Team With No Conflicts

[Java] LeetCode 1626. Best Team With No Conflicts

 

문   제 : 

당신은 감독으로써 농구대회에 나갈 선수들을 뽑아야 한다.

각 선수들의 나이와 점수가 주어진다. -> int[] ages, int[] scores

대회에 선수가 나갈 때에는 규칙이 있다.

1. 나이가 더 어린 선수가 나이가 많은 선수보다 score가 높으면 안된다.

2. 나이가 같다면 점수차이가 나도 상관없이 출전할 수 있다.

 

대회 규칙을 지키면서 가장 높은 scores를 기록하기 위해 출전할 선수들을 고르고 

그 선수들의 scores의 합을 구해라.

 

{ 1 <= scores.length, ages.length <= 1000 }

{ scores.length == ages.length }

{ 1 <= scores[i] <= 10^6 }

{ 1 <= ages[i] <= 1000 }

 

 

Example )

Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: It is best to choose the last 3 players.
Notice that you are allowed to choose multiple people of the same age.

///////////////////////////////////////////////

Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: It is best to choose the first 3 players.

 

---

접   근 : 

DP를 활용하여

선수들을 한 명씩 추가하며 더 큰 점수를 낼 수 있는 선수단을 고른다.

---

해   결 : 

선수 클래스를 생성한다.

정렬이 가능할 수 있도록 Comparable 인터페이스를 구현한다.

선수들을 나이순, 점수순으로 오름차순 정렬한다.

 

선수들을 한 명씩 추가해가며 그 선수가 추가되었을 때에 선수단에서 빠져야할 선수가 생기면

더 큰 점수를 얻게 할 수 있는 선수가 남는다.

 

---

선수 클래스 생성 & Comparable 인터페이스 구현

 

public class Player implements Comparable<Player>{
    public int scores;
    public int ages;

    public Player(int scores, int ages){
        this.scores = scores;
        this.ages = ages;
    }

    public int compareTo(Player p1){
        if(this.ages > p1.ages) return 1;
        else if(this.ages == p1.ages) {
            if(this.scores > p1.scores) return 1;
            else return -1;
        }
        else return -1;
    }
}

 

 

---

 

선수들을 List에 넣고 정렬

 

List<Player> players = new ArrayList<>();
for(int i=0; i<n; i++){
    players.add(new Player(scores[i], ages[i]));
}
Collections.sort(players); // ages, scores 오름차순 정렬

 

---

선수들을 한 명씩 넣으면서 그 전에 넣었었던 선수들과 비교해준다.

 

 

for(int i = 0; i < n; i++) {
    dp[i] = players.get(i).scores;
    for(int j = 0; j < i; j++) {
        if(players.get(j).scores <= players.get(i).scores) // 이전에 추가했던 사람의 점수가 작거나 같으면
            dp[i] = Math.max(dp[i], dp[j] + players.get(i).scores);
    }
    ans = Math.max(ans, dp[i]);
}

 

선수들의 수 만큼 반복하며 선수들을 추가해준다.

이전에 추가했던 선수의 점수가 작거나 같으면 - 경기를 같이 뛰어도 규칙에 어긋나지 않는 것을 의미한다.

따라서 더 큰 점수를 얻을 수 있는 선수단으로 최신화 해준다.

그리고 dp 배열에서 가장 큰 값을 가진 선수단이 경기에 나가게 된다.

---

결   과  :

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int dp[] = new int[n];
        int ans=0;

        List<Player> players = new ArrayList<>();
        for(int i=0; i<n; i++){
            players.add(new Player(scores[i], ages[i]));
        }
        Collections.sort(players); // age 오름차순 정렬
        
        for(int i = 0; i < n; i++) {
            dp[i] = players.get(i).scores;
            for(int j = 0; j < i; j++) {
                if(players.get(j).scores <= players.get(i).scores) // 이전에 추가했던 사람의 점수가 작거나 같으면
                    dp[i] = Math.max(dp[i], dp[j] + players.get(i).scores);
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;

    }
    public class Player implements Comparable<Player>{
        public int scores;
        public int ages;

        public Player(int scores, int ages){
            this.scores = scores;
            this.ages = ages;
        }

        public int compareTo(Player p1){
            if(this.ages > p1.ages) return 1;
            else if(this.ages == p1.ages) {
                if(this.scores > p1.scores) return 1;
                else return -1;
            }
            else return -1;
        }
    }

}