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

2024. 8. 19. 18:11·스터디/99클럽 코테 스터디 TIL
목차
  1. 📝 문제
  2. https://leetcode.com/problems/longest-increasing-subsequence/description/
  3. 🔥 시도해본 접근 방식
  4. 💦 풀이 실패

📝 문제

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;
    }
}

'스터디 > 99클럽 코테 스터디 TIL' 카테고리의 다른 글

99클럽 코테 스터디 31일차 점프 점프  (0) 2024.08.22
99클럽 코테 스터디 30일차 Find Right Interval  (0) 2024.08.21
99클럽 코테 스터디 28일차 괄호 회전하기  (0) 2024.08.19
99클럽 코테 스터디 27일차 할인 행사  (0) 2024.08.18
99클럽 코테 스터디 26일차 달리기 경주  (0) 2024.08.16
  1. 📝 문제
  2. https://leetcode.com/problems/longest-increasing-subsequence/description/
  3. 🔥 시도해본 접근 방식
  4. 💦 풀이 실패
'스터디/99클럽 코테 스터디 TIL' 카테고리의 다른 글
  • 99클럽 코테 스터디 31일차 점프 점프
  • 99클럽 코테 스터디 30일차 Find Right Interval
  • 99클럽 코테 스터디 28일차 괄호 회전하기
  • 99클럽 코테 스터디 27일차 할인 행사
Been
Been
  • Been
    Been
    Been
  • 전체
    오늘
    어제
    • 분류 전체보기 (60)
      • 언어 (0)
        • Kotlin (0)
      • 안드로이드 (17)
      • iOS (3)
      • Git (1)
      • 스터디 (39)
        • 알고리즘 문제 풀이 (1)
        • 99클럽 코테 스터디 TIL (38)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    코딩테스트준비
    maxWidth
    안드로이드
    자바
    쓰기권한
    깃
    항해99
    아이폰
    RecyclerView
    WRITE EXTERNAL
    풀이실패
    TIL
    Git
    java
    Coroutines
    개발자취업
    Android
    NSR
    debugRuntimeClasspath
    리싸이클러뷰
    객체변환
    nsl
    IOS
    EditText
    밑줄제거
    Androiod
    AndroidID
    FragmentStateAdapter
    99클럽
    언더라인 제거
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Been
99클럽 코테 스터디 29일차 Longest Increasing Subsequence
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.