99클럽 코테 스터디 29일차 Longest Increasing Subsequence

📝 문제

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

🔥 시도해본 접근 방식

주어진 배열을 활용하여 가능한 가장 긴 오름차순 배열을 만들어야 하는문제이므로,

1. 리스트하나를 선언

2. 해서 배열의 첫번째 원소부터 순회하여 리스트의 마지막 원소보다 크면 추가하고 작으면 리스트의 마지막 원소를 제거

위와 같은 방식으로 접근해보았다.

 

import java.util.ArrayList;

class Solution {
    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();

        for (int num : nums) {
            if (list.isEmpty() || list.get(list.size() - 1) < num) {
                list.add(num);
            } else if (list.get(list.size() - 1) > num) {
                list.remove(list.size() - 1);
                list.add(num);
            }
        }

        return list.size();
    }
}

위 처럼 코드를 작성해봤는데 실패하였다.

단순하게 리스트에 넣은 마지막 원소만 비교하는 방식은 맞지 않고

배치 할 수 있는 모든 경우의 수를 비교해야 한다는걸 깨달았다.

 

 

💦 풀이 실패

도저히 감이 잡히지 않아 Chat-gpt의 도움을 받았다.

 

이 문제는 DP로 풀리는 문제였고 nums 의 사이즈와 동일한 배열을 선언하여

첫번째 원소부터 진행하면서 해당 원소를 배치할 수 있을 때 배치된 배열의 길이를 

해당 인덱스에 기록하면서 마지막 까지 기록하고

가장 큰 원소를 답으로 반환하면 되는 문제였다.

 

여전히 문제를 보았을 때 어떤 알고리즘으로 접근해야 하는지 떠오르지 않는게 큰 문제인 것 같고

문제를 많이 풀어보는 수 밖에 없을 것 같다.

 

class Solution {
    public int lengthOfLIS(int[] nums) {
        final int[] dpArr = new int[nums.length];
        dpArr[0] = 1;
        int maxCount = 1;

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dpArr[i] = Math.max(dpArr[i], Math.max(dpArr[j], 1) + 1);

                    maxCount = Math.max(dpArr[i], maxCount);
                } else if (nums[i] < nums[j]) {
                    dpArr[i] = dpArr[i] > 0 ? dpArr[i] : 1;
                }
            }
        }

        return maxCount;
    }
}