리트코드 - 데일리과제(3/30) Russian Doll Envelopes

 

1. 접근법

 

다이나믹프로그래밍

 

2. 로직

 

이 문제는 LIS를 사전에 알아야 풀 수 있는 문제다.

 

LIS를 구현하는 법은 o(n^2) 부터 nlogn 까지 있다. 나같은 경우는 n^2으로 풀이를 했다.

 

1) 오른차순 정렬

2) 현재 인덱스 전까지 비교하며 메모리제이션 한다.

 

3. 코드

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>(){
           public int compare(int pair1[], int pair2[]){
               if(pair1[0] == pair2[0]){
                   return pair1[1] - pair2[1];
               }
               return pair1[0] - pair2[0];
           } 
        });
        int dp[] = new int[envelopes.length];
        int max=0;
        for(int i=0; i<envelopes.length; i++){
            dp[i] = 1;
            for(int j=0; j<i; j++){
                if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1] && dp[i]==dp[j]){
                    dp[i]++;
                }
            }
            max=Math.max(dp[i], max);
        }
        return max;
    }
}