2407. Longest Increasing Subsequence II ★★★★★★★★★★

2407. Longest Increasing Subsequence II

 

증가하는 서브시퀀스 구해서, 두개 차이가 <=k 인것만 남김

 

Longest Increasing Subsequence II (LeetCode 2407)

• nums: 정수 배열
• k: 최대 차이값

조건:

1. 엄격히 증가하는(subsequence) 부분 수열이어야 함 (즉, 이전 값보다 무조건 커야 함)
2. 인접한 값들의 차이 ≤ k 이어야 함 (nums[j] - nums[i] ≤ k where i < j)

➡️ 이런 조건을 만족하는 가장 긴 subsequence의 길이를 구하는 문제입니다.

 

"두 숫자 간 차이가 k 이하인 가장 긴 증가 부분 수열의 길이"를 세그먼트 트리를 사용해 빠르게 구하는 것

# 세그먼트 트리 클래스 정의
class SegmentTree:
    def __init__(self, N):
        self.n = N  # 트리에서 다룰 최대 인덱스 크기 (값의 범위)
        # 트리 노드 수를 2의 제곱수로 맞춰서 구현의 편의를 도모
        while (self.n & (self.n - 1)) != 0:  # 2의 거듭제곱이 아닐 때
            self.n += 1
        # 실제 트리 배열: 리프 노드 + 내부 노드 포함
        self.tree = [0] * (2 * self.n)  # 초기값 0으로 모두 채움

    # i 위치를 val 값으로 업데이트 (최댓값 갱신)
    def update(self, i, val):
        # 기존 값보다 작거나 같으면 굳이 업데이트 안 함 (최댓값 유지 목적)
        if val <= self.tree[self.n + i]:
            return
        # 리프 노드에 값 갱신
        self.tree[self.n + i] = val
        # 부모 노드로 올라가며 값 갱신
        j = (self.n + i) >> 1  # 부모 노드 인덱스
        while j >= 1:
            # 왼쪽 자식과 오른쪽 자식 중 최댓값으로 부모 노드 갱신
            self.tree[j] = max(self.tree[j << 1], self.tree[j << 1 | 1])
            j >>= 1  # 한 단계 위로 이동

    # 구간 [ql, qh]에 대한 최대값 질의
    def query(self, ql, qh):
        # 구간의 시작과 끝을 트리 배열 인덱스로 변환
        l = ql + self.n
        r = qh + self.n + 1  # 오른쪽은 exclusive (닫힌 구간 -> 반열림 구간으로 변환)
        res = 0  # 결과 저장 변수 (최댓값)

        # 구간을 좁혀가며 왼쪽과 오른쪽에서 필요한 값들을 가져옴
        while l < r:
            # 왼쪽 인덱스가 홀수라면, 해당 노드를 결과에 포함하고 오른쪽으로 한 칸 이동
            if l & 1:
                res = max(res, self.tree[l])
                l += 1
            # 오른쪽 인덱스가 홀수라면, 한 칸 왼쪽에 있는 노드를 포함하고 r은 줄임
            if r & 1:
                r -= 1
                res = max(res, self.tree[r])
            # 부모 노드로 이동
            l >>= 1
            r >>= 1
        return res  # 최종 최대값 반환

# 실제 문제 해결 클래스
class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        # nums 중 최대값을 찾아 트리 크기를 결정
        max_val = max(nums)
        # 값을 인덱스로 사용하기 위해 트리 크기를 max_val + 1로 생성
        ST = SegmentTree(max_val + 1)

        res = 0  # 정답 저장 변수 (최장 수열 길이)

        for num in nums:
            # num으로 끝나는 수열을 만들기 위해 num보다 작은 수 중에서 골라야 함
            # 그 중 num - k 이상인 값들만 유효하므로 구간은 [num - k, num - 1]
            l = max(0, num - k)       # 범위는 0보다 작아지면 안 되므로 max 사용
            r = max(0, num - 1)
            # 구간 [l, r]에서 가장 긴 수열의 길이를 구하고 +1 (현재 num 포함)
            curr = ST.query(l, r) + 1
            # 전체 최대값 갱신
            res = max(res, curr)
            # 현재 숫자 num 위치에 해당하는 값을 curr로 업데이트
            ST.update(num, curr)

        return res  # 최종 결과 반환

 

📌 요약 흐름

• 각 수 num을 처리할 때:
  1. num - k부터 num - 1까지의 구간에서 최대 수열 길이 찾기
  2. 그 길이에 +1 해서 num으로 끝나는 수열의 길이 구함
  3. 그 값을 트리에 업데이트함

---

🧠 기억 포인트 (코테용 핵심)

개념	설명
SegmentTree	빠른 구간 최대값 쿼리, 빠른 단일 업데이트
query(l, r)	O(log N)으로 [l, r] 구간의 최대값 구함
update(i, val)	i 위치의 값을 val로 갱신 (더 크면만 갱신)
nums[i] <= 10^5	가능하면 직접 인덱스 사용, 좌표 압축 생략 가능