백준 11053과 똑같은 문제이다.
주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하면 된다.
그런데 DP로 접근한 가장 긴 증가하는 부분 수열(11053) 풀이를 그대로 제출하면..
시간 초과가 뜬다.
입력 값의 범위가 다르기 때문이다.
이 문제는 입력의 최댓값이 1,000,000이므로,
시간 복잡도가 O(N^2)인 DP로 접근할 경우 시간 초과가 뜬다.
그래서 이 문제는 시간 복잡도를 고려해야 한다.
for문과 이진 탐색을 적절히 활용하면 O(NlogN)의 시간 복잡도를 갖는 코드를 짤 수 있다.
for문을 통해 순차적으로 수열의 원소를 탐색하면서 아래 항목을 체크한다.
[1] 현재 탐색 값이 정답 배열의 마지막 값보다 큰 경우
(1) 정답 배열 마지막 원소로 추가한다.
[2] 현재 탐색 값이 정답 배열의 마지막 값보다 크지 않은 경우
(1) 정답 배열에서 현재 탐색 값과 같은 값 또는 그 값보다 큰 값 중 가장 가까운 값의 위치를 찾는다. 이때, 정답 배열은 정렬되어 있는 셈이므로, 이진 탐색을 적용해도 된다.
(2) 현재 탐색 값을 해당 위치에 저장한다. (해당 위치의 값을 업데이트하는 것이다.)
2번째 과정이 필요한 이유는..
정답 배열 = [5, 7, 12], 남은 배열 = [9, 10]인 경우를 통해 확인할 수 있다.
만약 값을 업데이트하지 않는다면..
남은 배열을 모두 다 탐색했을 때, 정답 배열 = [5, 7, 12]로 정답은 3이 된다. (이는 오답이다.)
반대로 값을 업데이트해주면..
남은 배열을 모두 다 탐색했을 때, 정답 배열 = [5, 7, 9, 10]으로 정답은 4가 된다.
이때 값을 업데이트하면 주어진 수열에 존재하지 않는 LIS가 생성될 수 있는데,
문제에서 구하는 것은 LIS의 길이이므로 상관없다.
그러니까 정답 배열 = [5, 7, 12]인 상황에서 길이는 3인데,
다음 탐색 값인 9를 정답 배열의 어디에 업데이트하더라도 길이는 변하지 않는다.
코드(정답)는 다음과 같다.
import sys
def binary_search(lis, elem) -> int:
low, high = 0, len(lis) - 1
while low <= high:
mid = (low + high) // 2
if lis[mid] < elem:
low = mid + 1
else:
high = mid - 1
return low
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
lis = []
for elem in arr:
if not lis or elem > lis[-1]:
lis.append(elem)
else:
pos = binary_search(lis, elem)
lis[pos] = elem
print(len(lis))참고로 가장 긴 증가하는 부분 수열을 LIS라고도 부르는데,
Longest Increasing Subsequence의 약자이다.
