[Java] leetcode 1626. Best Team With No Conflicts

문제

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

Best Team With No Conflicts - LeetCode

알아야 할 개념

• DFS + 메모이제이션
• DP(Dynamic Programming) 

풀이

메모이제이션의 패러다임을 깬 문제. 

로직은 다음과 같다. 

1. 주어진 scores , ages 배열을 하나로 합친다. 
2. ages 기준 오름차순 정렬
3. 재귀 함수로 순차 탐색을 하면서, 2가지 행동을 한다.
4. 현재 인덱스 ( 현재 번호, 최댓값 번호 ) 를 메모이제이션 하여 중복 탐색을 피한다. 
5. 답을 리턴한다. 

 

ages를 기준으로 정렬하고 탐색을 하면서 2가지 행동을 한다. 

• 리스트 basketList 에 현재 플레이어를 포함시킨다. 
• 리스트 basketList 에 현재 플레이어를 포함하지 않고 넘어간다. 

재귀 함수의 현재 위치에서는 현재 탐색할 플레이어의 인덱스와 현재 baseketList 의 최댓값을 가진 플레이어의 인덱스 정보 (초기값 -1 ) 가 있다.

재귀 호출을 하면서 현재  플레이어보다 이전의 플레이어가 더 최댓값이면 2가지 행동을 모두 하고, 현재 basketList 최댓값보다 현재 플레이어값이 작으면 1가지 행동만 한다. 

 [ 현재 플레이어, 이전의 최댓값 ] 을 메모이제이션하여, 중복 탐색을 피한다.

 

참고

아래 그림은 위 알고리즘을 리트코드 예제 2번에 적용한 것이다. 

• 각 재귀에서 왼쪽은 현재 플레이어를 담는 것이고, 오른쪽은 담지 않는것이다.
• 초록색 [[]] 으로 basketList를 나타내였다.
• 살구색(cur, prev) 로나타내고, 현재 탐색할 curPlayer [ age, score ] 을 옆에 기술하였다. 
• 재귀 탐색은 dfs로 왼쪽으로 쭉 들어가고 그림을 따라 백트래킹 하면 이해가 편할 것이다. 

예제 2번을 시각화한 그림

 

코드

자바

class Solution {
    int memo[][];
    int ans = 0;
    
    public int bestTeamScore(int[] s, int[] age) {
        //<age, score>
       List<int[]> l = new ArrayList<>();
       int len = s.length;
       memo = new int[len][len+1];

       for(int i = 0; i< len ;i++){
           l.add(new int[]{age[i], s[i]});
       }

       Collections.sort(l, (a,b)->a[0]-b[0] == 0 ? a[1]-b[1]: a[0]-b[0]);

        return dfs(0,-1,l);
    }
    public int dfs(int cur, int prev, List<int[]>infoList){
        if( cur>= infoList.size() )return 0;
        else if(memo[cur][prev+1] > 0 )return memo[cur][prev+1];
        else{
            if(prev == -1 || infoList.get(prev)[1] <= infoList.get(cur)[1])
                return memo[cur][prev+1] = Math.max(dfs(cur+1, cur, infoList) + infoList.get(cur)[1], 
                                                    dfs(cur+1, prev, infoList));
            return memo[cur][prev+1] = dfs(cur+1, prev, infoList);
        }
    }
}