(25.05.12) 조건이 많은 경우의 LIS

기존에 보았던 간단한 LIS Longest Increasing Subsequence를 구하는 알고리즘의 확장되어 여러개의 조건을 비교하면서 Subsequence를 구해야하는 경우에 대해 정리를 하고자 한다.

 

즉, 1개의 조건을 만족하나 2번째 조건을 만족하는 경우까지 고려를 해 LIS를 구해야하고

1개의 조건이 동일한 경우, 2번쨰 조건에 따라 정렬하여 LIS를 구해야하는 것이다.  

---

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

DP 활용하기

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;

        // sort envelopes
        // width ASC
        Arrays.sort(envelopes, (a, b) -> {
            if(a[0] == b[0]) {
                return b[1] - a[1]; 
            }
        });

        // dp
        // val all the possibilities
        int[] dp = new int[n];

        // init
        Arrays.fill(dp, 1);

        // update DP
        // find max value at the same time
        int max = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j <i; j++) {
                // update when width and height are less than curr
                if(envelopes[i][0] > envelopes[j][0] &&
                envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

• DP 를 채우기 위해서 이중for문을 활용해서 가능한 많은 경우의 수를 업데이트 하는 알고리즘이다
  • 이중 for문이기 때문에 O(n^2) 시간 복잡도
• 모든 인덱스에서의 최대 경우의 수를 확인할 수 있음

→ 모든 예제가 통과 가능한 정상적인 알고리즘, 단**, TIME LIMIT 발생**

다중 조건에서의 LIS 적용

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;

        // sort envelopes
        // width ASC -> height DESC
        Arrays.sort(envelopes, (a, b) -> {
            if(a[0] == b[0]) {
                return b[1] - a[1]; 
            } else {
                return a[0] - b[0];
            }
        });

        // find LIS of Height
        List<Integer> lis = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            int height = envelopes[i][1];

            int index = Collections.binarySearch(lis, height);

            // no val
            if(index < 0) index = Math.abs(index) - 1;
 
            // more than lis
            if(index >= lis.size()) lis.add(height);

            // less than lis
            if(index < lis.size()) lis.set(index, height);

        }

        return lis.size();
    }
}

• LIS, Longest Increasing Subsequence를 활용해서 최대한 메모리를 적게 쓸 수 있어야함
  • binarySearch 를 활용하면서 업데이트 하기 때문에,  O(n log n) 시간복잡도 밖에 들지 못함
  • 엄격한 Increasing 조건 부합
    • 마트료시카 처럼 엄격하게 동일한 값은 허용하지 않고 무조건 큰 순서로 정렬해야하기 때문
    • 단, 중복도 포함한다면, lis 추가 for 문에서 중복 값을 카운트 해서 lis크기에 더하기만 하면 됨

두 가지 조건을 고려할 때의 LIS

• 한가지 조건을 중심(위에서는 높이 기준)으로 LIS를 찾아야하기 때문에, 미리 높이을 DESC 정렬을 해야함
• → 같은 너비 일 경우, 가장 작은 높이를 선택 하기 위해 lis.set(index, height); 에서 큰 높이를 먼저 세팅을 해야 int index = Collections.binarySearch(lis, height); 에서 앞으로 만들면서 최솟값으로 갱신
• 마찬가지로 여러가지 조건일 때, 앞선 조건들이 같더라도 작은 값으로 갱신해야하기 때문에 LIS가 적용될 수 있도록 맨 마지막만 내림차순으로 하면 가능

LDS 라면?

• 마트료시카가 아닌, 큰 봉투 → 작은 봉투 순서대로 가장 많이 넣는다고 가정한다면?

→ LIS 와 순서만 거꾸로 된 것일 뿐, 똑같이 진행만 하면 됨

---

여러가지 조건일 경우에는 일반적인 하나의 LIS를 구하는 것과 다르게 sort를 통해서 해당 조건을 DESC를해야하는 작업이 반드시 존재를 해야할 것이다.

 

간단한 알고리즘이지만 여러 조건이 나왔다는 점에 당황해서 일반적인 방법으로 적용하게 된다면, 최적의 가장 긴 값이 아닌 값이 나올 수 있기 때문에 반드시 고려를 해야할 것이다.