Softeer - 징검다리 (Python)

Lv3, ⭐⭐⭐

문제 풀이

• 문제의 설명부터 LIS라고 강하게 어필하고 있다.
• 오랜만에 LIS를 다시 봤다.
  • 물론 까먹어서 풀이를 다시 봄

1. DP 풀이

• 핵심 로직은 i까지 진행하면서 i이전의 j들 중에서 작은게 있다면, 해당 dp[j]에 +1
• O(N²)의 시간 복잡도를 가진다.

from sys import stdin
# Longest Increase Sequence

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
dp = [1 for _ in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:  # 이전 값보다 크면
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

2. 이분탐색(bisect) 풀이

• 핵심 로직 : bisect_left(arr, x) : arr가 정렬되어있다는 가정 하에, x가 들어갈 인덱스 반환
  • 현재 값이 가장 큰 값이라면, 뒤에 append()
    아니라면, 해당 값을 dp의 길이를 변화시키지 않으면서 값을 변경해준다.
• O(N logN)의 시간복잡도를 가진다.

from sys import stdin
import bisect

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
dp = [arr[0]]

for i in range(n):
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bisect.bisect_left(dp, arr[i])
        dp[idx] = arr[i]

print(len(dp))