[LeetCode] 300. Longest Increasing Subsequence - Java

https://leetcode.com/problems/longest-increasing-subsequence/description/

Longest Increasing Subsequence - LeetCode

---

문제

Given an integer array nums, return the length of the longest strictly increasing 

subsequence

.

 

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

 

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

 

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

---

풀이

풀이 과정

주어진 nums 배열에서 최장 증가 부분 수열의 길이를 찾아내는 문제이다.

최장 증가 부분 수열이란 수열 안에서 오름차순으로 증가하는 값들로 이루어진 부분 수열 중 가장 긴 부분 수열을 의미한다. 이 때 부분 수열의 값들은 연속하지 않아도 된다.

예시 )

[ 5, 1, 4, 7, 2, 9, 10 ] 수열이 있다고 할 때 오름차순으로 증가하는 값들로 이루어진 부분 수열은 다음과 같다.

[ 5, 1, 4, 7, 2, 9, 10 ] → 길이 : 4
[ 5, 1, 4, 7, 2, 9, 10 ] → 길이 : 5
[ 5, 1, 4, 7, 2, 9, 10 ] → 길이 : 4
[ 5, 1, 4, 7, 2, 9, 10 ] → 길이 : 4

이 부분 수열 중 길이가 가장 긴 [1, 4, 7, 9, 10] 이 최장 증가 부분 수열이 된다.

탐색값을 저장할 배열을 하나 선언한다. 이 배열은 각 인덱스 i 에 대해서 길이가 i인 부분 수열들의 원소 중 최솟값을 저장한다.

// 탐색결과를 저장할 배열 선언
// dp 배열은 항상 정렬된 상태로 유지되며
// dp배열의 원소의 길이가 최장 부분 증가 수열의 길이가 된다
int[] dp = new int[nums.length];
// 첫 번째 원소값 초기화
dp[0] = nums[0];

 

결과 값으로 return 할 변수를 하나 선언하고 nums 배열을 순회하며 각 요소들을 탐색한다.
현재 탐색값이 dp배열의 최장 길이 부분 수열의 마지막 값보다 크다면 다음 원소에 현재 탐색값을 저장하고 최장 길이를 증가시킨다.
만약 현재 탐색값이 dp 배열의 최장 길이 부분 수열의 마지막 값보다 크지 않다면 lowerBound를 이용하여 현재 탐색값보다 처음으로 값이 커지는 위치를 찾아 값을 갱신한다.

// nums 배열을 순회하며 탐색
for(int i = 1; i < nums.length; i++){
    // 현재 탐색값이 dp 배열의 마지막 값보다 크다면
    // 현재 탐색값을 다음원소에 추가하고 최장 길이 증가
    if(nums[i] > dp[maxLength - 1]){
        dp[maxLength] = nums[i];
        maxLength++;
    } 
    // 현재 탐색값이 dp 배열의 마지막 값보다 크지 않다면
    // lowerBound를 이용해 현재 탐색값이 들어갈 수 있는 최적 위치에 갱신한다
    else {
        lowerBound(dp, nums[i], 0, maxLength - 1);
    }
}

return maxLength;

// 오름차순으로 정렬된 배열에서
// n이 들어갈 수 있는 위치를 찾아 값을 갱신
public void lowerBound(int[] arr, int n, int start, int end){
    // 시작인덱스와 종료인덱스의 가운데 인덱스
    int mid;

    // 시작인덱스와 종료인덱스가 만날 때까지 반복
    while(start < end){
        // 가운데 인덱스 설정
        mid = (start + end) / 2;
        // 중앙값이 n보다 작다면 시작 인덱스를 mid + 1로 설정
        if(arr[mid] < n) start = mid + 1;
        // 중앙값이 n이상이라면 종료 인덱스를 mid로 설정
        else end = mid;
    }

    // 탐색이 종료되면 lowerBound 위치의 값을 n으로 갱신
    arr[end] = n;
}

---

최종 코드

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 탐색결과를 저장할 배열 선언
        // dp 배열은 항상 정렬된 상태로 유지되며
        // dp 배열의 원소의 길이가 최장 부분 증가 수열의 길이가 된다
        int[] dp = new int[nums.length];
        // 첫 번째 원소값 초기화
        dp[0] = nums[0];

        // 부분 증가 수열의 최장 길이
        int maxLength = 1;

        // nums 배열을 순회하며 탐색
        for(int i = 1; i < nums.length; i++){
            // 현재 탐색값이 dp 배열의 마지막 값보다 크다면
            // 현재 탐색값을 다음원소에 추가하고 최장 길이 증가
            if(nums[i] > dp[maxLength - 1]){
                dp[maxLength] = nums[i];
                maxLength++;
            } 
            // 현재 탐색값이 dp 배열의 마지막 값보다 크지 않다면
            // lowerBound를 이용해 현재 탐색값이 들어갈 수 있는 최적 위치에 갱신한다
            else {
                lowerBound(dp, nums[i], 0, maxLength - 1);
            }
        }

        return maxLength;
    }

    // 오름차순으로 정렬된 배열에서
    // n이 들어갈 수 있는 위치를 찾아 값을 갱신
    public void lowerBound(int[] arr, int n, int start, int end){
        // 시작인덱스와 종료인덱스의 가운데 인덱스
        int mid;

        // 시작인덱스와 종료인덱스가 만날 때까지 반복
        while(start < end){
            // 가운데 인덱스 설정
            mid = (start + end) / 2;
            // 중앙값이 n보다 작다면 시작 인덱스를 mid + 1로 설정
            if(arr[mid] < n) start = mid + 1;
            // 중앙값이 n이상이라면 종료 인덱스를 mid로 설정
            else end = mid;
        }

        // 탐색이 종료되면 lowerBound 위치의 값을 n으로 갱신
        arr[end] = n;
    }
}

---