[LeetCode] 491번 Non-decreasing Subsequences 문제를 풀어보았다. (ft. java)

2023년 01월 20일 금요일 - 어우 연휴 너무 조아!!!!

오늘 올려볼 문제는 491번 Non-decreasing Subsequences 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

생각보다는 어려워잉...

입력

사진에서도 볼 수 있듯이 int 배열 1개가 입력으로 들어온다.

---

풀이 및 코드

배열의 subsequnce를 구하는데 해당 subsequnce는 오름차순으로 정렬되어있어야한다. 또한 subsequnce는 unique 해야한다.

오늘은 처음부터 정답을 생각해냈다.

입력의 크기가 작다보니 브루트포스, 백트래킹 같았다.

unique 함을 처리해야하는데 오름차순인게 주어졌으니 스택과 마지막에 스택에 넣은 값을 기준으로 백트래킹을 진행했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    int[] arr;
    public List<List<Integer>> findSubsequences(int[] nums) {
        arr = nums;
        
        solve(0, -10000, new Stack<>());
        
        return result;
    }
    
    public void solve(int index, int prev, Stack<Integer> s) {
        if(index == arr.length) {
            if(s.size() > 1) result.add(new ArrayList(s));
            return;
        }
        
        if(prev <= arr[index]) {
            s.push(arr[index]);
            solve(index + 1, arr[index], s);
            s.pop();
        }
        if(prev != arr[index]) solve(index + 1, prev, s);
    }
}

---

제출 화면

요즘 리트코드가 할만해보이는데 어려운 문제를 자꾸 낸다...

조금만 더 쉽게 내줬으면 ㅠ

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.